P2756 飞行员配对方案问题
这是一个裸的二分图最大匹配问题，可以用匈牙利算法解决，当然也可以网络流的最大流解决。
我们将源点和每一个英国飞行员连一条边权为1的边，将每一个外籍飞行员和汇点连边权为1的边，再将每一对匹配的英军飞行员和外籍飞行员之间连一条边权为1的边。跑这个图的最大流，就得到了二分图的最大匹配。
\(code:\)
int main(){
scanf("%d%d",&m,&n);
while(1){
scanf("%d%d",&u,&v);
if(u==-1&&v==-1)
break;
add(u,v);
}
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j)
vis[j]=0;
if(dfs(i))
++ans;
}
printf("%d\n",ans);
for(int i=1;i<=n;++i)
if(match[i])
printf("%d %d\n",match[i],i);
return 0;
}
P2765魔术球问题
考虑每一个新放的球，它要么是单独放一个柱子上，要么是放到其他球上面。
我们将每一个球 \(i\) 拆成 \(i\) 和 \(i'\) 。将源点 \(s\) 和 \(i\) 连一条流量为1的边，再将 \(i'\) 和汇点 \(t\) 连一条流量为1的边，表示每一个球能且只能使用一次。
再考虑当前的球能放到哪些球上面。设这些球为 \(j\) ,那么再将 \(j\) 向 \(i'\) 连一条边权为1的边，表示 \(j\) 球后面能接 \(i\) 球。
这样，每放进一个球，就跑一遍 \(dinic\)，如果能够找到增广路，说明当前的球能放到其他球上面，否则说明当前的球只能自立门户。
\(code:\)
int dfs(int x,int sum){
if(x==t)
return sum;
int re=sum,k;
for(int i=now[x];i&&re;i=nxt[i])
if(d[ver[i]]==d[x]+1&&e[i]){
now[x]=i;
k=dfs(ver[i],min(re,e[i]));
if(!k)
d[ver[i]]=0;
else
nx[(x+1)>>1]=((ver[i]+1)>>1);
re-=k;e[i]-=k;e[i^1]+=k;
}
return sum-re;
}
int main(){
scanf("%d",&n);
s=0;t=10001;tot=1;
for(int i=1;i<=5000;++i){
//add(i*2-1,i*2,1);add(i*2,i*2-1,0);
add(s,i*2-1,1);add(i*2-1,s,0);
add(i*2,t,1);add(t,i*2,0);
for(int j=1;j*j<i*2;++j)
if(j*j-i>0)
add((j*j-i)*2-1,i*2,1),add(i*2,(j*j-i)*2-1,0);
int sum=0,f=0;
while(bfs())
while(sum=dfs(0,1e9))
f+=sum;
if(!f){
++cnt;box[cnt]=i;
}
if(cnt>n){
ans=i-1;break;
}
}
printf("%d\n",ans);
for(int i=1;i<=n;++i){
int x=box[i];
while(x!=(10001+1)/2&&x!=0){
printf("%d ",x);
x=nx[x];
}
printf("\n");
}
return 0;
}
P2754 [CTSC1999]家园 / 星际转移问题
看到时间，想到将每个节点拆成500个分点，代表时刻 \(1\)~\(500\) 。
假设某个飞船 \(t\) 时刻在节点 \(p[t]\) ，那么我们把节点 \(p[t]\) 的第 \(t\) 个分点连向节点 \(p[t+1]\) 的第 \(t+1\) 个分点，权值为该飞船容纳的人数 \(h\) 。以上过程模拟了飞船的周期性穿梭。
接下来，对于每一个节点的任何一个分点，向它的下一个分点连权值为 \(inf\) 的边，模拟人停留在某个星球。
最后是 \(s\) 向地球的第一个分点连权值为 \(k\) 的边，月球的每一个分点向汇点连一条权值为 \(inf\) 的边。
怎么判断是否无解以及最短时间呢？考虑二分答案。如果当前的时间为 \(t\) ，那么只能在每个点的第 \(1\)~\(t\) 个分点上跑最大流。如果当前最大流是 \(k\) ，说明所有人都能在 \(t\) 时间内转移到月球，符合题意；否则不符合题意。这样，就能二分出最短时间。而如果最大流永远达不到 \(k\) ，那么无解。
\(code:\)
int main(){
scanf("%d%d%d",&n,&m,&k);
tot=1;s=0;t=(n+2)*501+1;
for(int i=1;i<=m;++i){
scanf("%d%d",&h,&u);
for(int j=1;j<=u;++j){
scanf("%d",&p[j]);
if(p[j]==-1)
p[j]=n+2;
else
++p[j];
}
for(int j=1;j<=500;++j)
add(p[(j-1)%u+1]+(j-1)*(n+2),p[j%u+1]+j*(n+2),h),add(p[j%u+1]+j*(n+2),p[(j-1)%u+1]+(j-1)*(n+2),0);
//cout<<p[(j-1)%r+1]+(j-1)*(n+2)<<" "<<p[j%r+1]+j*(n+2)<<endl;
}
for(int i=1;i<=n+2;++i)
for(int j=1;j<=500;++j)
add(i+(n+2)*(j-1),i+(n+2)*j,1e9),add(i+(n+2)*j,i+(n+2)*(j-1),0);
add(0,1,k);add(1,0,0);
for(int i=1;i<=501;++i)
add((n+2)*i,t,1e9),add(t,(n+2)*i,0);
l=1,r=501;
while(l<r){
for(int i=1;i<=tot;++i)
edge[i]=e[i];
for(int i=0;i<=t;++i)
now[i]=0;
mid=(l+r)>>1;
int sum=0,f=0;
while(bfs())
while(sum=dfs(0,1e9))
f+=sum;
if(f<k)
l=mid+1;
else
r=mid;
}
if(r==501)
printf("0\n");
else
printf("%d\n",r-1);
return 0;
}