题面
UPD：COGS 貌似进不去了，链接失效就删掉了。
如果你不小心看到了题目评论区，那你就会知道这是一道双倍经验题，另一题的链接见题目评论区……
网络流+tarjan好题，但如果你真的的理解了网络流反向边的作用，那这就是一道大水题……
题目要求出一定在最大流中的边的数目，显然先跑网络流（废话），然后考虑到题目要求的是一定在最大流中的边，换就话说，这条边要不可替代，什么边不可替代呢——割边（大雾）连接着两个强连通分量的边。
为什么呢？
首先，我们要知道边满流的概念。对于正向边（并没有找到标准说法，若有知道的，评论告知），当且仅当他的流量等于容量（废话），在这道题中，就是一条匹配边（容量为一）；对于反向边，当且仅当他对应的正向边流量为零，在这道题中，就是一条未匹配边的反向边。（也许和标准定义不一样，就先这么理解这道题吧）
若一条边在某个强连通分量中，则这条边连接的两个点X—>Y，一定存在一条路径Y—>X，且这条路径上的边全部都是反向边，故原图中必然存在一条路径从X—>Y，且路径上的边全部都是未匹配边，即这条边不是不可替代的。
于是，我们就可以在满流的边上跑tarjan，然后枚举每一条满流的判断即可。
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <queue> 5 #include <stack> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <cstring> 10 #include <complex> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 #define rg register 15 #define ll long long 16 using namespace std; 17 18 inline int gi() 19 { 20rg int r = 0; rg bool b = 1; rg char c = getchar(); 21while ((c < '0' || c > '9') && c != '-') c = getchar(); 22if (c == '-') b = 0; 23while (c >= '0' && c <= '9') { r = (r << 1) + (r << 3) + c - '0', c = getchar(); } 24if (b) return r; return -r; 25 } 26 27 const int inf = 240002357, N = 1e5+5, M = 6e5+5; 28 int n,m,w,S,T,Time,num,mac[N],pre[N],f[N]; 29 int stc[N],scc[N],dep[N],dfn[N],low[N]; 30 queue <int> q; 31 struct Edge 32 { 33int to,nx,cap; 34 }eg[M]; 35 36 inline void add(int x,int y,int z) 37 { 38eg[++num]=(Edge){y,f[x],z}; f[x]=num; 39 } 40 41 inline int dfs(int o,int flow) 42 { 43if (!flow || o == T) 44 return flow; 45int i,to,cap,tmp,fl; 46fl=0; 47for (i=f[o]; i; i=eg[i].nx) 48 { 49 to=eg[i].to, cap=eg[i].cap; 50 if (dep[to] != dep[o]+1 || cap <= 0) 51 continue; 52 tmp=dfs(to,min(flow,cap)); 53 eg[i].cap-=tmp, eg[i^1].cap+=tmp; 54 fl+=tmp, flow-=tmp; 55 if (!flow) 56 break; 57 } 58if (!fl) 59 dep[o]=0; 60return fl; 61 } 62 63 inline int bfs() 64 { 65int i,o,to,cap; 66memset(dep,0,sizeof(dep)); 67q.push(S), dep[S]=1; 68while (!q.empty()) 69 { 70 o=q.front(), q.pop(); 71 for (i=f[o]; i; i=eg[i].nx) 72 { 73 to=eg[i].to, cap=eg[i].cap; 74 if (dep[to] || cap <= 0) 75continue; 76 dep[to]=dep[o]+1; 77 if (to == T) 78{ 79 while (!q.empty()) q.pop(); 80 break; 81} 82 q.push(to); 83 } 84 } 85return dep[T]; 86 } 87 88 inline int dinic() 89 { 90int flow; 91flow=0; 92while (bfs()) 93 flow+=dfs(S,inf); 94return flow; 95 } 96 97 inline void tarjan(int o) 98 { 99int i,to,cap;100dfn[o]=low[o]=++Time;101stc[++stc[0]]=o;102for (i=f[o]; i; i=eg[i].nx)103 {104 to=eg[i].to, cap=eg[i].cap;105 if (cap > 0)106 continue;107 if (!dfn[to])108 {109 tarjan(to);110 low[o]=min(low[to],low[o]);111 }112 else if (!scc[to])113 low[o]=min(low[o],dfn[to]);114 }115if (low[o] == dfn[o])116 {117 ++scc[T+1];118 do119 {120 to=stc[stc[0]--];121 scc[to]=scc[T+1];122 }123 while (to != o);124 }125 }126 127 int main()128 {129freopen("sphere.in","r",stdin);130freopen("sphere.out","w",stdout);131int i,x,y,ans,cap;132n=gi(), m=gi();133S=0, T=n+1, num=1, ans=0, n>>=1;134for (i=1; i<=m; i++)135 {136 x=gi(), y=gi();137 add(x,y,1), add(y,x,0);138 }139for (i=1; i<=n; ++i)140 {141 add(S,i,1), add(i,S,0);142 add(i+n,T,1), add(T,i+n,0);143 }144w=dinic();145for (i=S; i<=T; ++i)146 if (!dfn[i])147 tarjan(i);148m<<=1, m++;149for (i=2; i<=m; i+=2)150 {151 cap=eg[i].cap, x=eg[i].to, y=eg[i^1].to;152 if (cap > 0)153 continue;154 if (scc[x] != scc[y])155 ans++;156 }157printf("%d\n",ans);158return 0;159 }
如果觉得《COGS【345】共荣圈 【426】血帆海盗》对你有帮助，请点赞、收藏，并留下你的观点哦！
