hihoCoder感觉很好。
网络流的精华就是建图
#include#include #include #include #include using namespace std;struct node{ int point; int weight; int nxt;};node line[5000000];int head[50000],tail=-1;void add(int x,int y,int z){ line[++tail].point=y; line[tail].weight=z; line[tail].nxt=head[x]; head[x]=tail; line[++tail].point=x; line[tail].weight=0; line[tail].nxt=head[y]; head[y]=tail;}int cur[50000],dep[50000];bool BFS(int begin,int end){ for(int i=begin;i<=end;i++) { cur[i]=head[i]; dep[i]=0; } dep[begin]=1; queue q; q.push(begin); while(!q.empty()) { int pas=q.front(); q.pop(); for(int i=head[pas];i!=-1;i=line[i].nxt) if(!dep[line[i].point]&&line[i].weight) { dep[line[i].point]=dep[pas]+1; q.push(line[i].point); } } if(dep[end]) return true; return false;}int DFS(int now,int aim,int limte){ if(now==aim||!limte) return limte; int flow=0,f; for(int i=cur[now];i!=-1;i=line[i].nxt) { cur[now]=i; if(dep[line[i].point]==dep[now]+1&&(f=DFS(line[i].point,aim,min(limte,line[i].weight)))) { limte-=f; flow+=f; line[i].weight-=f; line[i^1].weight+=f; if(!limte) break; } } return flow;}int dinic(int begin,int end){ int res=0; while(BFS(begin,end)) res+=DFS(begin,end,0x7fffffff); return res;}//以上都是标准的dinic。ISAP就是个垃圾int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<=2*n+1;i++)//0为起点，2*n+1为终点 head[i]=-1; int a,b; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b+n,1); } for(int i=1;i<=n;i++) add(0,i,1); for(int i=1;i<=n;i++) add(n+i,2*n+1,1); int ans=dinic(0,2*n+1); printf("%d",n-ans);}