CF #165 DIV2 E 最大流的流向-白红宇

CF #165 DIV2 E 最大流的流向

阅读量：4114 次

发布时间：2019-05-25

本文共 1346 字，大约阅读时间需要 4 分钟。

给你n个节点,m条边组成的网络流，要求你求出每条边的流向；

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 using namespace std; typedef long long ll; typedef unsigned long long Ull; #define MM(a,b) memset(a,b,sizeof(a)); const double eps = 1e-10; const int inf = 0x3f3f3f3f; const double pi=acos(-1); const int mod=100000000; ll max(ll a,ll b) {return a>b?a:b;}; int min(int a,int b) {return a
                
                  G[200005]; ll deg[200005]; int ans[200005],vis[200005]; int main() { int n,m,u,v,c; while(~scanf("%d %d",&n,&m)) { for(int i=1;i<=n;i++) G[i].clear(); MM(deg,0);MM(vis,0); for(int i=1;i<=m;i++) { scanf("%d %d %d",&u,&v,&c); G[u].push_back((edge){v,c,i,0}); G[v].push_back((edge){u,c,i,1}); deg[u]+=c; deg[v]+=c; } queue
                 
                   q; q.push(1); while(q.size()) { int u=q.front();q.pop(); vis[u]=1; for(int i=0;i

分析：

题目不用求最大流，而是求每条边的流向，这题是考察网络流的基本规律。

若某图有最大，则有与源点相连的边必然都是流出的，与汇点相连的边必然是流入的，其它所有点流入和流出的流量是相等的。

我们可以根据这一规律来求解。

先求出所有点（除了源点和汇点）的总流量（表示流入的流量的2倍），每次流过该边，更新的时候减去流入流量的2倍。

从源点出发广搜每个点，搜的过程可以确定经过边的流向，当某个点的剩余总流量为0时，表示流入该点的流量边已经都处理完毕，将这点入栈。

特别注意：当这个点是汇点时不要入栈，不然会从汇点回流过来，不符合基本规律。

此外：这个算法的关键核心是，

if(v!=n) deg[v]-=2*G[u][i].c;

if(!deg[v]) q.push(v); 因为一旦当前节点流入该节点跟新了这个节点后，这个节点deg==0的话，那么从这个

节点出发的访问未访问过的节点就只能是从改点流出了

转载地址：http://mxgsi.baihongyu.com/

你可能感兴趣的文章

关于发烧用美林的转贴，（不代表个人观点，大家参考一下）