历年好题代码整理
Setsugesuka · · 个人记录
开车旅行
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const long long INF=1e15;
struct node
{
long long h;
int id;
node(){}
node(long long h,int id=0):h(h),id(id){}
bool operator <(const node &o) const
{
return h<o.h;
}
};
long long h[MAXN],ga[MAXN],gb[MAXN]; //h 海拔 ga[i] 从i开始向右最近的城市 gb[i] 从i开始向右第二近的城市
long long dp[30][MAXN][2],da[30][MAXN][2],db[30][MAXN][2]; //dp[i][j][0/1] 从j开始开 开到最近/第二近的那个人先开 开2^i次到达的城市 da[i][j][0/1] 从j开始开 开到最近/第二近的那个人先开 开到最近的那个人开的距离
long long la,lb; // a和b开的距离
int n,m,cctot=0,t,sr,srpos;
set<node> s; // 计算ga和gb用
node cc[7];
inline long long getdis(int x,int y)
{
return abs(h[x]-h[y]);
}
inline void calc(int st,int x)
{
int p=st;
la=0,lb=0;
for(int i=t;i>=0;i--)
{
if(dp[i][p][1]&&la+lb+da[i][p][1]+db[i][p][1]<=x) //如果还可以开
{
lb=lb+da[i][p][1];
la=la+db[i][p][1];
p=dp[i][p][1];
}
}
}
int main()
{
scanf("%d",&n);
t=(int)(log(n)/log(2))+1;
for(int i=1;i<=n;i++)
scanf("%lld",&h[i]);
for(int i=1;i<=n;i++)
s.insert(node(h[i],i));
for(int i=1;i<=n;i++)//每次找到前驱 前驱的前驱 后继 后继的后继 找最小和次小
{
s.erase(s.find(node(h[i],i)));
cctot=0;
set<node>::iterator it=s.lower_bound(node(h[i]));
if(it!=s.end())
{
cc[++cctot]=*it;
++it;
if(it!=s.end())
cc[++cctot]=*it;
}
it=s.lower_bound(node(h[i]));
if(it!=s.begin())
{
--it;
cc[++cctot]=*it;
if(it!=s.begin())
{
--it;
cc[++cctot]=*it;
}
}
if(cctot==0)
ga[i]=gb[i]=0;
else if(cctot==1)
ga[i]=cc[1].id,gb[i]=0;
else
{
node fmx=node(INF),smx=node(INF);
for(int j=1;j<=cctot;j++)
{
if(abs(cc[j].h-h[i])<abs(fmx.h-h[i]))
{
smx=fmx;
fmx=cc[j];
}
else if(abs(cc[j].h-h[i])==abs(fmx.h-h[i])&&fmx.h>cc[j].h)
{
smx=fmx;
fmx=cc[j];
}
else if(abs(cc[j].h-h[i])==abs(smx.h-h[i])&&smx.h>cc[j].h)
{
smx=cc[j];
}
else if(abs(cc[j].h-h[i])<abs(smx.h-h[i]))
{
smx=cc[j];
}
}
ga[i]=fmx.id;
gb[i]=smx.id;
}
}
for(int j=1;j<=n;j++)
dp[0][j][0]=ga[j],dp[0][j][1]=gb[j]; //开2^0=1天都是直接开
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=0;k<=1;k++)
{
if(i==1)
dp[1][j][k]=dp[0][dp[0][j][k]][1-k];//注意到i=1的时候 2^(i-1)=1 不是偶数 所以要换成1-k去开
else
dp[i][j][k]=dp[i-1][dp[i-1][j][k]][k];
}
}
}
for(int j=1;j<=n;j++)
da[0][j][0]=getdis(j,ga[j]),da[0][j][1]=0;
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=0;k<=1;k++)
{
if(i==1)
da[1][j][k]=da[0][j][k]+da[0][dp[0][j][k]][1-k];
else
da[i][j][k]=da[i-1][j][k]+da[i-1][dp[i-1][j][k]][k];
}
}
}
for(int j=1;j<=n;j++)
db[0][j][0]=0,db[0][j][1]=getdis(j,gb[j]);
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=0;k<=1;k++)
{
if(i==1)
db[1][j][k]=db[0][j][k]+db[0][dp[0][j][k]][1-k];
else
db[i][j][k]=db[i-1][j][k]+db[i-1][dp[i-1][j][k]][k];
}
}
}
scanf("%d",&sr);
calc(1,sr);
long long ans1=la,ans2=lb;
int ans=1;
for(int i=2;i<=n;i++)
{
calc(i,sr);
if(la*ans2<lb*ans1) //防止精度丢失
{
ans1=la;
ans2=lb;
ans=i;
}
}
printf("%d\n",ans);
scanf("%d",&m);
while(m--)
{
scanf("%d %d",&srpos,&sr);
calc(srpos,sr);
printf("%lld %lld\n",la,lb);
}
return 0;
}疫情控制
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
struct edge
{
int u,v,nex;
long long w;
};
struct node
{
long long rest;
int pos;
node(){}
node(long long rest,int pos):rest(rest),pos(pos) {}
};
edge e[MAXN<<1];
int head[MAXN],cnt=0;
int fa[MAXN][30],t;
long long dis[MAXN];
bool haszhu[MAXN];
queue<int> q;
int pos[MAXN],dep[MAXN];
long long restpoint[MAXN];
vector<node> restarmy1,restarmy2;
bool flag;
int n,m,pointtot;
inline void add(int u,int v,long long w)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt;
}
inline void bfs()
{
dep[1]=1;
q.push(1);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(dep[v]) continue;
dep[v]=dep[u]+1;
dis[v]=dis[u]+e[i].w;
fa[v][0]=u;
for(int j=1;j<=t;j++)
fa[v][j]=fa[fa[v][j-1]][j-1];
q.push(v);
}
}
}
inline void init()
{
memset(haszhu,false,sizeof(haszhu));
pointtot=0;
restarmy1.clear();
restarmy2.clear();
flag=false;
}
inline bool cmp(node x,node y)
{
return x.rest<y.rest;
}
void dfs(int u)
{
if(haszhu[u]) return;
bool ccflag=false;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa[u][0]) continue;
ccflag=true;
dfs(v);
}
if(!ccflag)//如果是叶子节点 说明没有被驻守
flag=true;
return;
}
inline bool check(long long nowtime)
{
init();//初始化
for(int i=1;i<=m;i++)
{
int ccpos=pos[i];
long long cctime=nowtime;
for(int j=t;j>=0;j--)
{
if(fa[ccpos][j]>1&&dis[ccpos]-dis[fa[ccpos][j]]<=cctime)//如果还可以跳 就向上跳
{
cctime-=dis[ccpos]-dis[fa[ccpos][j]];
ccpos=fa[ccpos][j];
}
}
if(fa[ccpos][0]==1&&dis[ccpos]<=cctime)//如果可以到达根
{
if(dis[ccpos]*2<=cctime)
restarmy1.push_back(node(cctime-dis[ccpos],ccpos));//1存可以到根还可以回来的
else
restarmy2.push_back(node(cctime,ccpos));//2存到了根就回不来的
}
else
haszhu[ccpos]=true;
}
for(int i=head[1];i;i=e[i].nex)
{
int v=e[i].v;
flag=false;
dfs(v);
if(!flag)
haszhu[v]=true;//如果子树所有的叶子都不会被访问了 那么这个子树就被驻守了
}
for(int i=0;i<restarmy2.size();i++)
{
if(!haszhu[restarmy2[i].pos])
haszhu[restarmy2[i].pos]=true;//如果它所在的子树没有被驻守 且自己到了根就回不来了 显然是自己驻守自己比较优
else
restarmy1.push_back(node(restarmy2[i].rest-dis[restarmy2[i].pos],restarmy2[i].pos));//否则我们加进可以移动的队列里面
}
for(int i=head[1];i;i=e[i].nex)
{
int v=e[i].v;
if(!haszhu[v])
restpoint[++pointtot]=dis[v];
}
if(!pointtot) return true;//如果所有的点都被驻守了 返回true
sort(restarmy1.begin(),restarmy1.end(),cmp);
sort(restpoint+1,restpoint+pointtot+1);
int nowpoint=1;
for(int i=0;i<restarmy1.size();i++)//剩余时间最短的军队去路程最短的节点
{
if(restpoint[nowpoint]<=restarmy1[i].rest)
nowpoint++;
if(nowpoint>pointtot)
return true;
}
return false;
}
int main()
{
scanf("%d",&n);
t=(int)(log(n)/log(2))+1;
for(int i=1;i<n;i++)
{
int x,y;
long long z;
scanf("%d %d %lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&pos[i]);
}
bfs();
long long l=0,r=500000,ans=-1;
while(l<=r) //二分答案
{
int mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}货车运输
#include<bits/stdc++.h>
using namespace std;
const int INF=1e8;
const int MAXN=1e4+10;
const int MAXM=5e4+10;
struct edge
{
int u,v,nex;
int w;
};
struct trenode
{
int ans;
int ls,rs,l,r;
};
edge e[MAXM<<1],kru_e[MAXM];
trenode tre[MAXN<<2];
int head[MAXN],cnt=0,trecnt=0;
int kru_fa[MAXN];
int val[MAXN],fa[MAXN],dep[MAXN],id[MAXN],rk[MAXN],top[MAXN],sz[MAXN],son[MAXN],dfscnt=0;
int which[MAXN],trert[MAXN],tot=0;
int n,m,q,rt;
inline void add(int u,int v,long long w)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt;
}
inline bool cmp(edge x,edge y)
{
return x.w>y.w;
}
int find(int x)
{
if(kru_fa[x]==x) return x;
else return kru_fa[x]=find(kru_fa[x]);
}
inline void kru()
{
sort(kru_e+1,kru_e+1+m,cmp);
for(int i=1;i<=m;i++)
{
int fu=find(kru_e[i].u),fv=find(kru_e[i].v);
if(fu==fv) continue;//如果已经联通就忽略
kru_fa[fu]=fv;
add(kru_e[i].u,kru_e[i].v,kru_e[i].w);
add(kru_e[i].v,kru_e[i].u,kru_e[i].w);
}
}
void dfs1(int u)
{
sz[u]=1;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa[u]) continue;
dep[v]=dep[u]+1;
fa[v]=u;
val[v]=e[i].w;//边权转点权
which[v]=which[u];
dfs1(v);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;
id[u]=++dfscnt;
rk[dfscnt]=u;
if(!son[u]) return;
dfs2(son[u],tp);
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
inline void pushup(int x)
{
tre[x].ans=min(tre[tre[x].ls].ans,tre[tre[x].rs].ans);
}
void build(int l,int r,int x)
{
if(l==r)
{
tre[x].l=tre[x].r=l;
tre[x].ans=val[rk[l]];
return;
}
int mid=(l+r)>>1;
tre[x].ls=++trecnt,tre[x].rs=++trecnt;
build(l,mid,tre[x].ls);
build(mid+1,r,tre[x].rs);
tre[x].l=tre[tre[x].ls].l;
tre[x].r=tre[tre[x].rs].r;
pushup(x);
}
int query(int L,int R,int x)
{
if(L<=tre[x].l&&tre[x].r<=R)
{
return tre[x].ans;
}
int mid=(tre[x].l+tre[x].r)>>1,ret=INF;
if(L<=mid)
ret=min(ret,query(L,R,tre[x].ls));
if(R>mid)
ret=min(ret,query(L,R,tre[x].rs));
return ret;
}
inline int sum(int x,int y)
{
int ret=INF;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret=min(ret,query(id[top[x]],id[x],rt));
x=fa[top[x]];
}
if(id[x]>id[y]) swap(x,y);
ret=min(ret,query(id[x]+1,id[y],rt));//注意id[x]存的是x->fa[x]的边 和我们要的无关
return ret;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) kru_fa[i]=i;
for(int i=1;i<=m;i++)
scanf("%d %d %d",&kru_e[i].u,&kru_e[i].v,&kru_e[i].w);//做最大生成树用
kru();
for(int i=1;i<=n;i++)
{
if(!dep[i])//如果访问到一棵新的树
{
tot++;
dep[i]=1;
which[i]=tot;
trert[tot]=i;//记录好根
dfs1(i);
}
}
for(int i=1;i<=tot;i++)
dfs2(trert[i],trert[i]);//给每棵树做一次重链剖分
build(1,n,rt=++trecnt);
scanf("%d",&q);
while(q--)
{
// cout<<q<<endl;
int x,y;
scanf("%d %d",&x,&y);
if(which[x]!=which[y])//判断是否联通
puts("-1");
else
printf("%d\n",sum(x,y));
}
return 0;
}运输计划
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=3e5+10;
inline char nc()
{
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &sum)
{
char ch=nc();
int tf=0;
sum=0;
while((ch<'0'||ch>'9')&&(ch!='-')) ch=nc();
tf=((ch=='-')&&(ch=nc()));
while(ch>='0'&&ch<='9') sum=sum*10+(ch-48),ch=nc();
(tf)&&(sum=-sum);
}
struct edge
{
int u,v,w,nex;
};
struct node
{
int x,y,dis,lca;
};
node nodes[MAXN];
edge e[MAXN<<1];
int head[MAXN],cnt=0;
int dep[MAXN],fa[MAXN][30],dis[MAXN],val[MAXN],t;
queue<int> q;
int n,m,rt,l,r,ans;
inline void add(int u,int v,int w)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt;
}
void bfs()
{
dep[rt]=1;
q.push(rt);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(dep[v]) continue;
dep[v]=dep[u]+1;
fa[v][0]=u;
dis[v]=dis[u]+e[i].w;
val[v]=e[i].w;
for(int j=1;j<=t;j++)
fa[v][j]=fa[fa[v][j-1]][j-1];
q.push(v);
}
}
}
inline int lca(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
for(int i=t;i>=0;--i)
{
if(dep[fa[y][i]]>=dep[x]) y=fa[y][i];
}
if(x==y) return x;
for(int i=t;i>=0;--i)
{
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int tot,sum[MAXN];
int mxdis,mxedge;
void dfs(int u)
{
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa[u][0]) continue;
dfs(v);
sum[u]+=sum[v];
}
if(sum[u]==tot)
mxedge=max(mxedge,val[u]);
}
inline void init()
{
for(int i=1;i<=n;++i) sum[i]=0;
tot=0,mxdis=-1,mxedge=-1;
}
inline bool check(int mid)
{
init();
for(int i=1;i<=m;++i)
{
if(nodes[i].dis>mid)
{
mxdis=max(mxdis,nodes[i].dis);
++sum[nodes[i].x];
++sum[nodes[i].y];
sum[nodes[i].lca]-=2;
++tot;
}
}
if(!tot) return true;
dfs(rt);
if(mxdis-mxedge<=mid) return true;
return false;
}
int main()
{
read(n),read(m);
t=(int)(log(n)/log(2))+1;
rt=(rand()%n)+1;
l=0,r=0;
for(int i=1;i<n;++i)
{
int x,y,z;
read(x),read(y),read(z);
add(x,y,z);
add(y,x,z);
}
bfs();
for(int i=1;i<=m;++i)
{
read(nodes[i].x),read(nodes[i].y);
nodes[i].lca=lca(nodes[i].x,nodes[i].y);
nodes[i].dis=dis[nodes[i].x]+dis[nodes[i].y]-2*dis[nodes[i].lca];
r=max(r,nodes[i].dis);
}
ans=-1;
l=r-1000;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}天天爱跑步
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
struct edge
{
int u,v,nex;
};
edge e[MAXN<<1];
int head[MAXN],cnt=0;
int fa[MAXN][22],dep[MAXN],t;
int cc1[MAXN<<1],cc2[MAXN<<1],ans[MAXN],val[MAXN];
vector<pair<int,int> >op1[MAXN],op2[MAXN];
queue<int> q;
int n,m;
inline void add(int u,int v)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].nex=head[u];
head[u]=cnt;
}
inline void bfs()
{
dep[1]=1;
q.push(1);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(dep[v]) continue;
fa[v][0]=u;
dep[v]=dep[u]+1;
for(int j=1;j<=t;j++)
fa[v][j]=fa[fa[v][j-1]][j-1];
q.push(v);
}
}
}
inline int lca(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
for(int i=t;i>=0;--i)
{
if(dep[fa[y][i]]>=dep[x]) y=fa[y][i];
}
if(x==y) return x;
for(int i=t;i>=0;--i)
{
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
inline void update(int s,int t)
{
int cclca=lca(s,t);
op1[s].push_back(make_pair(dep[s],1));
op1[fa[cclca][0]].push_back(make_pair(dep[s],-1));
op2[t].push_back(make_pair(dep[s]-2*dep[cclca]+n,1));
op2[cclca].push_back(make_pair(dep[s]-2*dep[cclca]+n,-1));
}
void dfs(int u)
{
int tmp1=val[u]+dep[u],tmp2=val[u]-dep[u]+n;
int res1=cc1[tmp1],res2=cc2[tmp2];
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa[u][0]) continue;
dfs(v);
}
for(int i=0;i<op1[u].size();i++)
cc1[op1[u][i].first]+=op1[u][i].second;
for(int i=0;i<op2[u].size();i++)
cc2[op2[u][i].first]+=op2[u][i].second;
ans[u]=(cc1[tmp1]-res1)+(cc2[tmp2]-res2);
}
int main()
{
scanf("%d %d",&n,&m);
t=(int)(log(n)/log(2))+1;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
bfs();
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
update(x,y);
}
dfs(1);
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}赛道修建
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int MAXN=50010;
struct edge
{
int u,v,nex;
long long w;
};
edge e[MAXN<<1];
int head[MAXN],cnt=0;
int n,m;
long long l,r,ans;
inline void add(int u,int v,long long w)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt;
}
long long len[MAXN],sum[MAXN];
multiset<long long> s[MAXN];
void dfs(int u,int fa,long long lim)
{
s[u].clear();
sum[u]=0;
len[u]=0;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u,lim);
len[v]+=e[i].w;
if(len[v]>=lim) sum[u]++;
else s[u].insert(len[v]);
}
long long mx=0;
while(!s[u].empty())
{
if(s[u].size()==1)
{
mx=max(mx,*s[u].begin());
s[u].erase(s[u].find(*s[u].begin()));
break;
}
multiset<long long>::iterator it=s[u].lower_bound(lim-*s[u].begin());
if(it==s[u].begin()&&s[u].count(*it)==1) it++;
if(it==s[u].end())
{
mx=max(mx,*s[u].begin());
s[u].erase(s[u].find(*s[u].begin()));
}
else
{
sum[u]++;
s[u].erase(s[u].find(*it));
s[u].erase(s[u].find(*s[u].begin()));
}
}
len[u]=mx;
return;
}
inline bool check(long long mid)
{
long long ret=0;
dfs(1,0,mid);
for(int i=1;i<=n;i++)
ret+=sum[i];
if(ret>=m) return true;
return false;
}
int main()
{
scanf("%d %d",&n,&m);
l=0,r=0,ans=-1;
for(int i=1;i<n;i++)
{
int x,y;
long long z;
scanf("%d %d %lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
r+=z;
}
r/=m;
while(l<=r)
{
long long mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}最优贸易
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=5e5+10;
struct edge
{
int u,v,w,nex;
};
edge e[(MAXM<<1)*5];
int head[(MAXN)*5],cnt=0;
int val[MAXN],dis[(MAXN)*5];
bool vis[(MAXN)*5];
queue<int> q;
int n,m;
inline void add(int u,int v,int w)
{
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt;
}
inline void spfa()
{
memset(dis,0x80,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[1]=0,vis[1]=true;
q.push(1);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v;
if(dis[v]<dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v])
{
q.push(v);
vis[v]=true;
}
}
}
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
for(int i=1;i<=m;i++)
{
int x,y,op;
scanf("%d %d %d",&x,&y,&op);
add(x,y,0);
add(x+n,y+n,0);
add(x+2*n,y+2*n,0);
if(op==2)
{
add(y,x,0);
add(y+n,x+n,0);
add(y+2*n,x+2*n,0);
}
}
for(int i=1;i<=n;i++)
{
add(i,i+n,-val[i]);
add(i+n,i+2*n,val[i]);
}
spfa();
printf("%d\n",dis[3*n]);
return 0;
}关押罪犯
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
const long long INF=1e15;
struct node
{
int x,y;
long long val;
};
node nodes[MAXN];
int fa[MAXN<<1];
int n,m;
inline bool cmp(node x,node y)
{
return x.val>y.val;
}
int find(int x)
{
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d %lld",&nodes[i].x,&nodes[i].y,&nodes[i].val);
}
for(int i=1;i<=(n<<1);i++)
fa[i]=i;
sort(nodes+1,nodes+1+m,cmp);
for(int i=1;i<=m;i++)
{
int fx1=find(nodes[i].x),fx2=find(nodes[i].x+n),fy1=find(nodes[i].y),fy2=find(nodes[i].y+n);
if(fx1==fy1||fx2==fy2)
{
printf("%lld\n",nodes[i].val);
return 0;
}
fa[fx1]=fy2;
fa[fy1]=fx2;
}
puts("0");
return 0;
}蚯蚓
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+10;
long long a[MAXN],ans[MAXN];
queue<long long> q1,q2,q3;
long long delta=0;
int n,m,q,u,v,t,tot=0;
inline bool cmp(long long x,long long y)
{
return x>y;
}
inline long long get()
{
long long val1=-1e15,val2=-1e15,val3=-1e15;
if(!q1.empty()) val1=q1.front();
if(!q2.empty()) val2=q2.front();
if(!q3.empty()) val3=q3.front();
if(val1>=val2&&val1>=val3)
{
q1.pop();
return val1;
}
if(val2>=val1&&val2>=val3)
{
q2.pop();
return val2;
}
if(val3>=val1&&val3>=val2)
{
q3.pop();
return val3;
}
}
inline void put(long long val1,long long val2)
{
if(val1<val2) swap(val1,val2);
q2.push(val1),q3.push(val2);
return;
}
int main()
{
scanf("%d %d %d %d %d %d",&n,&m,&q,&u,&v,&t);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++) q1.push(a[i]);
for(int i=1;i<=m;i++)
{
ans[i]=get()+delta;
long long cc1=ans[i]*u/v,cc2=ans[i]-cc1;
delta+=q;
put(cc1-delta,cc2-delta);
}
while(!q1.empty()||!q2.empty()||!q3.empty()) a[++tot]=get()+delta;
for(int i=t;i<=m;i+=t)
{
printf("%lld ",ans[i]);
}
puts("");
for(int i=t;i<=tot;i+=t)
{
printf("%lld ",a[i]);
}
puts("");
return 0;
}愤怒的小鸟
#include<bits/stdc++.h>
using namespace std;
const int MAXN=21;
const double eps=1e-6;
int lines[MAXN][MAXN],lownotbit[1<<MAXN],dp[1<<MAXN];
int n,m,T;
double x[MAXN],y[MAXN];
inline void get(double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2)
{
y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
x=(c1-b1*y)/a1;
}
int main()
{
for(int i=0;i<(1<<18);i++)
{
int j=1;
for(;j<=18&&(i&(1<<(j-1)));j++);
lownotbit[i]=j;
}
scanf("%d",&T);
while(T--)
{
memset(lines,0,sizeof(lines));
memset(dp,0x3f3f3f3f,sizeof(dp));
dp[0]=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lf %lf",&x[i],&y[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(fabs(x[i]-x[j])<eps) continue;
double a,b;
get(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
if(a>-eps) continue;
for(int k=1;k<=n;k++)
{
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps)
{
lines[i][j]|=(1<<(k-1));
}
}
}
}
for(int i=0;i<(1<<n);i++)
{
int j=lownotbit[i];
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);
for(int k=1;k<=n;k++)
{
dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1);
}
}
printf("%d\n",dp[(1<<n)-1]);
}
return 0;
}宝藏
#include<bits/stdc++.h>
using namespace std;
const int MAXN=21;
const int INF=1e9+7;
int mp[MAXN][MAXN],dis[MAXN],dp[MAXN][1<<15][MAXN];
int n,m,ans=INF;
void dfs(int state,int sum,int dep)
{
if(sum>=ans)
return;
if(state==(1<<n)-1)
{
ans=min(ans,sum);
return;
}
for(int i=1;i<=n;i++)
{
if(!((1<<(i-1))&state)) continue;
for(int j=1;j<=n;j++)
{
if(!((1<<(j-1))&state)&&mp[i][j]<1e9)
{
if(dp[j][1<<(j-1)|state][dep+1]<=sum+dis[i]*mp[i][j]) continue;
dp[j][1<<(j-1)|state][dep+1]=sum+dis[i]*mp[i][j];
dis[j]=dis[i]+1;
dfs(1<<(j-1)|state,dp[j][1<<(j-1)|state][dep+1],dep+1);
}
}
}
}
int main()
{
scanf("%d %d",&n,&m);
memset(mp,0x3f3f3f3f,sizeof(mp));
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
mp[x][y]=mp[y][x]=min(mp[x][y],z);
}
for(int i=1;i<=n;i++)
{
memset(dis,0,sizeof(dis));
memset(dp,0x3f3f3f3f,sizeof(dp));
dis[i]=1;
dfs(1<<(i-1),0,0);
}
printf("%d\n",ans);
return 0;
}