BZOJ1191: [HNOI2006]超级英雄Hero

这题标解是改一下匈牙利算法，显然，像我这种从不用匈牙利的人，会找个办法用网络流…
具体做法是这样，二分最后的答案ans，然后对前ans个问题建图跑网络流，看最大流能不能到ans。
  1 /**************************************************************
  2     Problem: 1191
  3     User: zhuohan123
  4     Language: C++
  5     Result: Accepted
  6     Time:64 ms
  7     Memory:3128 kb
  8 ****************************************************************/
  9  
 10 #include <iostream>
 11 #include <cstdio>
 12 #include <queue>
 13 #include <algorithm>
 14 #include <cstring>
 15 using namespace std;
 16 int head[11000],pointsize;
 17 struct edge{int to,next,c,p;};
 18 edge g[110000];int gnum=1;
 19 void addedge(int from,int to,int c)
 20 {
 21     g[++gnum].to=to;g[gnum].c=c;g[gnum].next=head[from];head[from]=gnum;
 22     g[++gnum].to=from;g[gnum].c=0;g[gnum].next=head[to];head[to]=gnum;
 23 }
 24 int dfsstart,dfsend,ans;
 25 bool haveans;int dfsans;
 26 int d[11000],vd[11000];
 27 void dfs(int po)
 28 {
 29     if(po==dfsend)
 30     {
 31         ans+=dfsans;
 32         haveans=true;
 33         return ;
 34     }
 35     int mind=pointsize-1,tempans=dfsans;
 36     for(int i=head[po];i;i=g[i].next)
 37     if(g[i].c)
 38     {
 39         if(d[g[i].to]+1==d[po])
 40         {
 41             if(g[i].c<dfsans)dfsans=g[i].c;
 42             dfs(g[i].to);
 43             if(d[dfsstart]>=pointsize)return ;
 44             if(haveans)
 45             {
 46                 g[i].c-=dfsans;
 47                 g[i^1].c+=dfsans;
 48                 return ;
 49             }
 50             dfsans=tempans;
 51         }
 52         if(d[g[i].to]<mind)mind=d[g[i].to];
 53     }
 54     vd[d[po]]--;
 55     if(!vd[d[po]])d[dfsstart]=pointsize;
 56     d[po]=mind+1;vd[d[po]]++;
 57 }
 58 int isap(int start,int end)
 59 {
 60     ans=0;
 61     memset(d,0,sizeof(d));
 62     memset(vd,0,sizeof(vd));
 63     vd[0]=pointsize;
 64     dfsstart=start;
 65     dfsend=end;
 66     while(d[dfsstart]<pointsize)
 67     {
 68         dfsans=2147483647;
 69         haveans=false;
 70         dfs(dfsstart);
 71     }
 72     return ans;
 73 }
 74 int n,m;
 75 int mj[1100][2];
 76 bool check(int po)
 77 {
 78     gnum=1;memset(head,0,sizeof(head));
 79     for(int i=1;i<=n;i++)addedge(n+m+1,i,1);
 80     for(int i=1;i<=po;i++)addedge(i+n,n+m+2,1);
 81     pointsize=n+m+2;
 82     for(int i=1;i<=po;i++)
 83     {
 84         addedge(mj[i][0]+1,i+n,1);
 85         addedge(mj[i][1]+1,i+n,1);
 86     }
 87     return po==isap(n+m+1,n+m+2);
 88 }
 89 int imerge(int l,int r)
 90 {
 91     if(l==r)return l;
 92     int mid=(l+r)/2+1;
 93     if(check(mid))return imerge(mid,r);
 94     else return imerge(l,mid-1);
 95 }
 96 int main(int argc ,char *argv[])
 97 {
 98     scanf("%d%d",&n,&m);
 99     for(int i=1;i<=m;i++)scanf("%d%d",&mj[i][0],&mj[i][1]);
100     printf("%d
",imerge(1,m));
101     return 0;
102 }