这道题基本上来就能看的出来是网络流但难点在于它的结果貌似与最大流，最小割都没啥关系，我猜不少萌新像我一样想暴力枚举边（要是考试我就真这么做了），但很明显，出题人没打算让你这么水过，100000的数据不是闹着玩的。因此我们需要更深的思考。
不知道有没有人和我一样，想最大流跑一边，然后再统计已匹配上的点，看它是否有能连接的点未被连接。但很容易举出反例，如:
2
13
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{ 11bool zr; 12int to,l,next; 13int from; 14 }road[500005]; 15 void build(int x,int y){ 16zz++; 17road[zz].zr=1; 18road[zz].to=y; 19road[zz].next=a[x]; 20road[zz].from=x; 21road[zz].l=1; 22a[x]=zz; 23zz++; 24road[zz].zr=0; 25road[zz].to=x; 26road[zz].next=a[y]; 27road[zz].from=y; 28road[zz].l=0; 29a[y]=zz; 30 } 31 int s,t; 32 int deep[100005]; 33 bool bfs(){ 34memset(deep,0,sizeof(deep)); 35deep[s]=1; 36queue<int> q1; 37q1.push(s); 38while(!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} 52if(!deep[t])return 0; 53else return 1; 54 } 55 int cur[100005]; 56 int dfs(int x,int sum){ 57if(x==t||!sum)return sum; 58for(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} 73return 0; 74 } 75 int work(){ 76int ans=0; 77while(bfs()) 78{ 79 int x; 80 memcpy(cur,a,sizeof(a)); 81 while(x=dfs(s,0x7fffffff)) 82 ans+=x; 83} 84return 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){ 90zz2++; 91dfn[x]=low[x]=zz2; 92rz[x]=rz2[x]=1; 93top++; 94st[top]=x; 95for(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}111if(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(){125freopen("bloodsail.in","r",stdin);126freopen("bloodsail.out","w",stdout);127scanf("%d%d",&n,&m);128t=n+1;129for(int i=1;i<=m;i++)130{131 int x,y;132 scanf("%d%d",&x,&y);133 build(x,y);134}135for(int i=1;i<=n;i++)136{137 if(i<=n/2) build(s,i);138 else build(i,t);139}140int an=work();141for(int i=0;i<=n+1;i++)142{143 if(!rz2[i])144 tarjan(i);145}146for(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}150printf("%d\n",sum);151 // while(1);152return 0;153 }
安利一发，“共荣圈”也是本题。
如果觉得《cogs426血帆海盗（网络流打法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
