COGS【345】共荣圈 && 【426】血帆海盗

题面

UPD：COGS 貌似进不去了，链接失效就删掉了。

如果你不小心看到了题目评论区，那你就会知道这是一道双倍经验题，另一题的链接见题目评论区……

网络流+tarjan好题，但如果你真的的理解了网络流反向边的作用，那这就是一道大水题……

题目要求出一定在最大流中的边的数目，显然先跑网络流（废话），然后考虑到题目要求的是一定在最大流中的边，换就话说，这条边要不可替代，什么边不可替代呢——割边（大雾）连接着两个强连通分量的边。

为什么呢？

首先，我们要知道边满流的概念。对于正向边（并没有找到标准说法，若有知道的，评论告知），当且仅当他的流量等于容量（废话），在这道题中，就是一条匹配边（容量为一）；对于反向边，当且仅当他对应的正向边流量为零，在这道题中，就是一条未匹配边的反向边。（也许和标准定义不一样，就先这么理解这道题吧）

若一条边在某个强连通分量中，则这条边连接的两个点X—>Y，一定存在一条路径Y—>X，且这条路径上的边全部都是反向边，故原图中必然存在一条路径从X—>Y，且路径上的边全部都是未匹配边，即这条边不是不可替代的。

于是，我们就可以在满流的边上跑tarjan，然后枚举每一条满流的判断即可。

 #include <map>

 #include <set>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstring>

 #include <complex>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 #define rg register

 #define ll long long

 using namespace std;

 inline int gi()

 {

     rg int r = ; rg bool b = ; rg char c = getchar();

     while ((c < '' || c > '') && c != '-') c = getchar();

     if (c == '-') b = ;

     while (c >= '' && c <= '') { r = (r << ) + (r << ) + c - '', c = getchar(); }

     if (b) return r; return -r;

 }

 const int inf = , N = 1e5+, M = 6e5+;

 int n,m,w,S,T,Time,num,mac[N],pre[N],f[N];

 int stc[N],scc[N],dep[N],dfn[N],low[N];

 queue <int> q;

 struct Edge

 {

     int to,nx,cap;

 }eg[M];

 inline void add(int x,int y,int z)

 {

     eg[++num]=(Edge){y,f[x],z}; f[x]=num;

 }

 inline int dfs(int o,int flow)

 {

     if (!flow || o == T)

         return flow;

     int i,to,cap,tmp,fl;

     fl=;

     for (i=f[o]; i; i=eg[i].nx)

         {

             to=eg[i].to, cap=eg[i].cap;

             if (dep[to] != dep[o]+ || cap <= )

                 continue;

             tmp=dfs(to,min(flow,cap));

             eg[i].cap-=tmp, eg[i^].cap+=tmp;

             fl+=tmp, flow-=tmp;

             if (!flow)

                 break;

         }

     if (!fl)

         dep[o]=;

     return fl;

 }

 inline int bfs()

 {

     int i,o,to,cap;

     memset(dep,,sizeof(dep));

     q.push(S), dep[S]=;

     while (!q.empty())

         {

             o=q.front(), q.pop();

             for (i=f[o]; i; i=eg[i].nx)

                 {

                     to=eg[i].to, cap=eg[i].cap;

                     if (dep[to] || cap <= )

                         continue;

                     dep[to]=dep[o]+;

                     if (to == T)

                         {

                             while (!q.empty()) q.pop();

                             break;

                         }

                     q.push(to);

                 }

         }

     return dep[T];

 }

 inline int dinic()

 {

     int flow;

     flow=;

     while (bfs())

         flow+=dfs(S,inf);

     return flow;

 }

 inline void tarjan(int o)

 {

     int i,to,cap;

     dfn[o]=low[o]=++Time;

     stc[++stc[]]=o;

     for (i=f[o]; i; i=eg[i].nx)

         {

             to=eg[i].to, cap=eg[i].cap;

             if (cap > )

                 continue;

             if (!dfn[to])

                 {

                     tarjan(to);

                     low[o]=min(low[to],low[o]);

                 }

             else if (!scc[to])

                 low[o]=min(low[o],dfn[to]);

         }

     if (low[o] == dfn[o])

         {

             ++scc[T+];

             do

                 {

                     to=stc[stc[]--];

                     scc[to]=scc[T+];

                 }

             while (to != o);

         }

 }

 int main()

 {

     freopen("sphere.in","r",stdin);

     freopen("sphere.out","w",stdout);

     int i,x,y,ans,cap;

     n=gi(), m=gi();

     S=, T=n+, num=, ans=, n>>=;

     for (i=; i<=m; i++)

         {

             x=gi(), y=gi();

             add(x,y,), add(y,x,);

         }

     for (i=; i<=n; ++i)

         {

             add(S,i,), add(i,S,);

             add(i+n,T,), add(T,i+n,);

         }

     w=dinic();

     for (i=S; i<=T; ++i)

         if (!dfn[i])

             tarjan(i);

     m<<=, m++;

     for (i=; i<=m; i+=)

         {

             cap=eg[i].cap, x=eg[i].to, y=eg[i^].to;

             if (cap > )

                 continue;

             if (scc[x] != scc[y])

                 ans++;

         }

     printf("%d\n",ans);

     return ;

 }

巴特西

COGS【345】共荣圈 && 【426】血帆海盗

最新文章

热门文章