刚学网络流的我这里有一道非常好的"网络流练手题"------[HNOI2006]超级英雄.
记得很久以前真的有这个节目来着,还是大兵主持的.
其实这是一道匈牙利板子大水题,但对于我们这种刚学网络流的 juruo 碰到什么题不用网络流做就非常的不爽,于是就有了这个 超级英雄 网络流+二分版.
这里直接二分答案,每次将源点和所有的锦囊连边,容量为1;再将锦囊和对应的问题连边,容量为1;最后是将问题和汇点T连边,容量还是1.然后跑一波Dinic,看是否满流,这道"网络流练手题就搞定了".
最后再吐槽一下:这道题的网络流打法非常非常优秀(比匈牙利慢而且代码量翻倍),没事干的时候可以打着玩儿......
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define inf (1<<30)
#define maxn (300050)
#define maxm (300050)
#define ll long long
#define il inline
#define RG register
using namespace std;
il int gi(){
RG int x=0,q=1; RG char ch=getchar();
while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();
if( ch=='-' ) q=-1,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
return q*x;
}
int S,T,n,m,num=1,F,que[maxn*5],level[maxn];
struct data{ int a,b; }ques[maxn];
int head[maxn],nxt[maxm],to[maxm],w[maxm];
il void add( int u,int v,int d ){
nxt[++num]=head[u];to[num]=v;w[num]=d;head[u]=num;
nxt[++num]=head[v];to[num]=u;w[num]=0;head[v]=num; }
il bool bfs(){
for(int i=S;i<=T;i++) level[i]=0;
que[0]=S,level[S]=1;
RG int hd=0,tl=1;
while(hd<tl){
RG int x=que[hd++];
if(x==T) return true;
for(int i=head[x];i;i=nxt[i]){
RG int v=to[i];
if(w[i] && !level[v]){
level[v]=level[x]+1;
que[tl++]=v;
}
}
}
return false;
}
il int dfs(RG int x,RG int maxf){
if(x==T) return maxf;
RG int ans=0;
for(RG int i=head[x];i;i=nxt[i]){
RG int v=to[i],f=w[i];
if(level[v]==level[x]+1 && f){
RG int minn=min(f,maxf-ans);
f=dfs(v,minn);
w[i]-=f,w[i^1]+=f,ans+=f;
if(ans==maxf) break;
}
}
if(!ans) level[x]=0;
return ans;
}
il void Dinic(){ while(bfs()) F+=dfs(S,inf); }
il bool check(int mid){
memset(head,0,sizeof(head)); num=1; F=0;
for(int i=1;i<=n;i++) add(S,i,1);
for(int i=1;i<=mid;i++){
add(ques[i].a,i+n,1); add(ques[i].b,i+n,1); add(i+n,T,1);
}
Dinic();
if(F>=mid) return 1;
else return 0;
}
il void init(){
n=gi(),m=gi();S=0,T=n+m+1;
for(int i=1;i<=m;i++) ques[i].a=gi()+1,ques[i].b=gi()+1;
}
il void work(){
int l=0,r=m,ans=0;
while(l<=r){
RG int mid=(l+r)>>1;
if( check(mid) ) l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
}
int main(){ init(); work(); return 0; }
最后顺便再附上匈牙利版代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[1001][1001],club[1001];
int n,m;
bool vis[1001];
bool dfs(int x){
for(int i=0;i<n;i++)
if(!vis[i]&&map[x][i]){
vis[i]=1;
if( !club[i]||dfs(club[i]) ){ club[i]=x; return true; }
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
map[i][x]=map[i][y]=1;
}
int ans=0;
for(int i=1;i<=m;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
else break;
}
printf("%d\n",ans);
return 0;
}