HDU6598 Harmonious Army

红太狼 2021-09-30 05:24 200阅读 0赞

经典网络流模型，可以看一下论文（浅析一类最小割问题(pty)）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjM5ODQ0_size_16_color_FFFFFF_t_70]  
 问 题 转 化 为 所 有 的 贡 献 − 最 小 割 a + b = B + C ( 考 虑 都 在 A 集 合 ， 即 花 费 为 B + C ) − − − − − − − ( 1 ) c + d = B + A ( 考 虑 都 在 B 集 合 ， 即 花 费 为 B + A ) − − − − − − − ( 2 ) a + d + e = A + C ( 考 虑 一 个 在 A ， 一 个 在 B ， 即 花 费 为 A + C ) − − ( 3 ) b + c + e = A + C ( 考 虑 一 个 在 A ， 一 个 在 B ， 即 花 费 为 A + C ) − − ( 4 ) 问题转化为所有的贡献-最小割 \\\\ a+b = B+C(考虑都在A集合，即花费为B+C) ------- (1)\\\\ c+d = B+A(考虑都在B集合，即花费为B+A) ------- (2)\\\\ a+d+e = A+C(考虑一个在A，一个在B，即花费为A+C)--(3)\\\\ b+c+e = A+C(考虑一个在A，一个在B，即花费为A+C)--(4)\\\\ 问题转化为所有的贡献−最小割a\+b=B\+C(考虑都在A集合，即花费为B\+C)−−−−−−−(1)c\+d=B\+A(考虑都在B集合，即花费为B\+A)−−−−−−−(2)a\+d\+e=A\+C(考虑一个在A，一个在B，即花费为A\+C)−−(3)b\+c\+e=A\+C(考虑一个在A，一个在B，即花费为A\+C)−−(4)  
 ( 4 ) + ( 3 ) − ( 2 ) − ( 1 ) (4)+(3)-(2)-(1) (4)\+(3)−(2)−(1)得 2 e = A + C − 2 B 2e=A+C-2B 2e=A\+C−2B  
考虑一个直观的解  
 a = b = ( B + C ) / 2 a=b=(B+C)/2 a=b=(B\+C)/2  
 c = d = ( B + A ) / 2 c=d=(B+A)/2 c=d=(B\+A)/2  
 e = ( A + C − 2 B ) / 2 e=(A+C-2B)/2 e=(A\+C−2B)/2  
整体乘2，最后最小割算出来/2即可

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    mt19937 mrand(random_device{ }());
    const ll mod=1000000007;
    int rnd(int x) {  return mrand() % x;}
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    
    const int maxn = 1e3+100;
    const int maxm = 1e5+100;
    const int inf = 0x7f7f7f7f;
    
    typedef struct Dinic
    { 
        typedef struct Edge
        { 
            int u,v,w,nxt;	
        } Edge;
        int head[maxn],hcnt;
        int dep[maxn];
        int cur[maxn];
        Edge e[maxm];
        int S,T,N;
        void init()
        { 
            memset(head,-1,sizeof head);
            hcnt = 0;
            S = T = N = 0;
        }
        void adde(int u,int v,int w)
        { 
            e[hcnt].u = u,e[hcnt].v = v,e[hcnt].w = w;
            e[hcnt].nxt = head[u];head[u] = hcnt++;
            e[hcnt].u = v,e[hcnt].v = u,e[hcnt].w = 0;
            e[hcnt].nxt = head[v];head[v] = hcnt++;
        }
        int  bfs()
        { 
            rep(i,0,N)
            { 
                dep[i] = inf;
            }
            queue<int> q;
            q.push(S); dep[S] = 0;
            while(!q.empty())
            { 
                int u = q.front();q.pop();
                for(int i = head[u];~i;i = e[i].nxt)
                { 
                    int v = e[i].v,w = e[i].w;
                    if(w > 0 && dep[u] + 1 < dep[v])
                    { 
                        dep[v] = dep[u] + 1;
                        if(v == T)
                        { 
                            return 1;
                        }
                        q.emplace(v);
                    }
                }
            }
            return dep[T] != inf;
        }
        int dfs(int s,int mw)
        { 
            if(s == T) return mw;
            for(int i = cur[s];~i;i=e[i].nxt)
            { 
                cur[s] = i;
                int v = e[i].v,w=e[i].w;
                if(w <= 0 || dep[v] != dep[s] + 1)
                { 
                    continue;
                }
                int cw = dfs(v,min(w,mw));
                if(cw <= 0)
                    continue;
                e[i].w -= cw;
                e[i^1].w += cw;
                return cw;				
            }
            return 0;
        }
        ll dinic()
        { 
            ll res = 0;
            while(bfs())
            { 
                rep(i,0,N)
                { 
                    cur[i] = head[i];
                }
                while(int d = dfs(S,inf))
                { 
                    res += 1ll * d;
                }
            }
            return res;
        }
    }  Dinic;
    
    int n,m,s,t;
    
    ll w[maxn],ww[maxn];
    int main(int argc, char const *argv[])
    { 
        while(scanf("%d%d",&n,&m)!=EOF)
        { 
        	memset(w,0,sizeof w);memset(ww,0,sizeof ww);
            Dinic din;din.init();
            s = 0,t = n+1;
            din.S = 0,din.T = n+1,din.N = n+10;
           	int u,v;
           	ll a,b,c;
           	ll ans = 0;
           	rep(i,0,m)
           	{ 	
           		scanf("%d%d%lld%lld%lld",&u,&v,&a,&b,&c);
           		// cout << "---------" << endl;
           		w[u] += b+c;w[v]+=b+c;
           		ww[u] += a+b;ww[v]+=a+b;
           		din.adde(u,v,a+c-2*b);
           		din.adde(v,u,a+c-2*b);
           		ans += a + b + c;
           	}
           	// cout << ans << endl;
           	rep(i,1,n+1)
           	{ 
           		din.adde(s,i,w[i]);
           		din.adde(i,t,ww[i]);
           	}
            printf("%lld\n",ans-din.dinic()/2 );
        }	
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MjM5ODQ0_size_16_color_FFFFFF_t_70]: /images/20210907/820a141848eb4aa38ed97338881d0975.png