cogs426血帆海盗（网络流打法）

　　这道题基本上来就能看的出来是网络流但难点在于它的结果貌似与最大流，最小割都没啥关系，我猜不少萌新像我一样想暴力枚举边（要是考试我就真这么做了），但很明显，出题人没打算让你这么水过，100000的数据不是闹着玩的。因此我们需要更深的思考。

　　不知道有没有人和我一样，想最大流跑一边，然后再统计已匹配上的点，看它是否有能连接的点未被连接。但很容易举出反例，如:

　　　　　　　　　　　　　 1 3

　　　　　　　　　　　　　 1 4

　　　　　　　　　　　　　 2 3

　　　　　　　　　　　 2 4

　　有些边是可以互相替换的，对于这点我们是束手无策了，那么能否通过搜索查证呢？

　　这就是本题的关键了，tarjan大法，直接用tarjan求出强联通分量，若有一些边可互相替换则他们一定在一个强联通分量里（原因留给读者思考）否则就说明该边无可替代，也就是我们要求的解得一部分。

　　在这里膜拜一下呵呵酵母菌神犇，是他告诉我一个“坑”（对我来说），我们所枚举的边一定在求最大流的时候被清算过，因此对于没有出现在最大流中的边需要直接忽略。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 #include<algorithm>
  7 #include<cmath>
  8 using namespace std;
  9 int n,m,zz=1,a[100005];
 10 struct ro{
 11     bool zr;
 12     int to,l,next;
 13     int from;
 14 }road[500005];
 15 void build(int x,int y){
 16     zz++;
 17     road[zz].zr=1;
 18     road[zz].to=y;
 19     road[zz].next=a[x];
 20     road[zz].from=x;
 21     road[zz].l=1;
 22     a[x]=zz;
 23     zz++;
 24     road[zz].zr=0;
 25     road[zz].to=x;
 26     road[zz].next=a[y];
 27     road[zz].from=y;
 28     road[zz].l=0;
 29     a[y]=zz;
 30 }
 31 int s,t;
 32 int deep[100005];
 33 bool bfs(){
 34     memset(deep,0,sizeof(deep));
 35     deep[s]=1;
 36     queue<int> q1;
 37     q1.push(s);
 38     while(!q1.empty())
 39     {
 40         int x=q1.front();
 41         q1.pop();
 42         for(int i=a[x];i>0;i=road[i].next)
 43         {
 44             int y=road[i].to;
 45             if((!deep[y])&&road[i].l>0)
 46             {
 47                 deep[y]=deep[x]+1;
 48                 q1.push(y);
 49             }
 50         }
 51     }
 52     if(!deep[t])return 0;
 53     else return 1;
 54 }
 55 int cur[100005];
 56 int dfs(int x,int sum){
 57     if(x==t||!sum)return sum;
 58     for(int i=cur[x];i>0;i=road[i].next)
 59     {
 60         int y=road[i].to;
 61         cur[x]=i;
 62         if(road[i].l>0&&deep[y]==deep[x]+1)
 63         {
 64             int k=dfs(y,min(sum,road[i].l));
 65             if(k)
 66             {
 67                 road[i].l-=k;
 68                 road[i^1].l+=k;
 69                 return k;
 70             }
 71         }
 72     }
 73     return 0;
 74 }
 75 int work(){
 76     int ans=0;
 77     while(bfs())
 78     {
 79         int x;
 80         memcpy(cur,a,sizeof(a));
 81         while(x=dfs(s,0x7fffffff))
 82             ans+=x;
 83     }
 84     return ans;
 85 }
 86 int st[100005],top,zz3,belong[100005];
 87 bool rz[100005],rz2[100005];
 88 int dfn[100005],low[100005],zz2;
 89 void tarjan(int x){
 90     zz2++;
 91     dfn[x]=low[x]=zz2;
 92     rz[x]=rz2[x]=1;
 93     top++;
 94     st[top]=x;
 95     for(int i=a[x];i>0;i=road[i].next)
 96     {
 97         int y=road[i].to;
 98         if(road[i].l>0) 
 99         {
100             if(!rz2[y])
101             {
102                 tarjan(y);
103                 low[x]=min(low[x],low[y]);
104             }
105             else if(rz[y])
106             {
107                 low[x]=min(low[x],dfn[y]);
108             }
109         }
110     }
111     if(low[x]==dfn[x])
112     {
113         int v;
114         zz3++;
115         do{
116             v=st[top];
117             top--;
118             belong[v]=zz3;
119             rz[v]=0;
120         }while(dfn[v]!=low[v]);
121     }
122 }
123 int sum;
124 int main(){
125     freopen("bloodsail.in","r",stdin);
126     freopen("bloodsail.out","w",stdout);
127     scanf("%d%d",&n,&m);
128     t=n+1;
129     for(int i=1;i<=m;i++)
130     {
131         int x,y;
132         scanf("%d%d",&x,&y);
133         build(x,y);
134     }
135     for(int i=1;i<=n;i++)
136     {
137         if(i<=n/2) build(s,i);
138         else build(i,t);
139     }
140     int an=work();
141     for(int i=0;i<=n+1;i++)
142     {
143         if(!rz2[i])
144             tarjan(i);
145     }
146     for(int i=2;i<=2*m+1;i+=2)
147     {
148         if(!road[i].l&&belong[road[i].from]!=belong[road[i].to]) sum++;
149     }
150     printf("%d
",sum);
151 //    while(1);
152     return 0;
153 }

安利一发，“共荣圈”也是本题。