HDU 4940 Destroy Transportation system（无源汇有上下界最大流）

看不懂题解以及别人说的集合最多只有一个点。。。。。

然后试了下题解的方法http://blog.sina.com.cn/s/blog_6bddecdc0102uzka.html

首先是无源汇有上下界最大流：就是最大流基础上，无源汇，每条边的流量有上下界。

这题是给一个图，V<=200，E<=5000，每条边有destroy[i][j]和build[i][j]。选一个非空点集S，令T为S的补集。若max{∑D[s][t]-D[t][s]-B[t][s]}<=0输出happy否则输出unhappy，其中s，t是点集S，点集T的结点。

转换的推导证明可以看题解链接。这里不说多成累赘。

对于无源汇有上下界最大流的解法如下http://blog.csdn.net/z309241990/article/details/38531655

上界用ci表示，下界用bi表示。

下界是必须流满的，那么对于每一条边，去掉下界后，其自由流为ci– bi。

主要思想：每一个点流进来的流=流出去的流

对于每一个点i，令

Mi= sum(i点所有流进来的下界流)– sum(i点所有流出去的下界流)

如果Mi大于0，代表此点必须还要流出去Mi的自由流，那么我们从源点连一条Mi的边到该点。

如果Mi小于0，代表此点必须还要流进来Mi的自由流，那么我们从该点连一条Mi的边到汇点。

如果求S->T的最大流，看是否满流(S的相邻边都流满)。

满流则有解，否则无解。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

// sap

#define mxn 222

#define mxe 10100

const int INF = 2100000000;

struct SAP{

    int dis[mxn], pre[mxn], gap[mxn], arc[mxn], f[mxe], cap[mxe];

    int head[mxn], nxt[mxe], vv[mxe], e;

    void init(){e=0;memset(head,-1,sizeof(head));}

    void add(int u,int v,int c) {

        vv[e] = v, cap[e] = c, nxt[e] = head[u], head[u] = e++;

        vv[e] = u, cap[e] = 0, nxt[e] = head[v], head[v] = e++;

    }

    int max_flow( int s, int t, int n ) {

        int q[mxn], j, mindis, ans = 0, ht = 0, tl = 1, u, v, low;

        bool found, vis[mxn];

        memset( dis, 0, sizeof(dis) );

        memset( gap, 0, sizeof(gap) );

        memset( vis, 0, sizeof(vis) );

        memset( arc, -1, sizeof(arc) );

        memset( f, 0, sizeof(f) );

        q[0] = t; vis[t] = true; dis[t] = 0; gap[0] = 1;

        while( ht < tl ) {

            u = q[ht++];

            for( int i = head[u]; i != -1; i = nxt[i] ) {

                v = vv[i];

                if( !vis[v] ) {

                    vis[v] = true;

                    dis[v] = dis[u] + 1;

                    q[tl++] = v;

                    gap[dis[v]]++;

                    arc[v] = head[v];

                }

            }

        }

        u = s; low = INF; pre[s] = s;

        while( dis[s] < n ) {

            found = false;

            for( int &i = arc[u]; i != -1; i = nxt[i] )

                if( dis[vv[i]] == dis[u]-1 && cap[i] > f[i] ) {

                    found = true; v = vv[i];

                    low = min(low, cap[i]-f[i]);

                    pre[v] = u; u = v;

                    if( u == t ) {

                        while( u != s ) {

                            u = pre[u];

                            f[arc[u]] += low;

                            f[arc[u]^1] -= low;

                        }

                        ans += low; low = INF;

                    }

                    break;

                }

            if( found )

                continue;

            mindis = n;

            for(int i = head[u]; i != -1; i = nxt[i] ) {

                if( mindis > dis[vv[i]] && cap[i] > f[i] ) {

                    mindis = dis[vv[j = i]];

                    arc[u] = i;

                }

            }

            gap[dis[u]]--;

            if( gap[dis[u]] == 0 ) return ans;

            dis[u] = mindis + 1;

            gap[dis[u]]++;

            u = pre[u];

        }

        return ans;

    }

}net;

int low[222];

int main(){

    int t,n,m,ca=0;

    scanf("%d",&t);

    while(t--){

        printf("Case #%d: ",++ca);

        scanf("%d%d",&n,&m);

        net.init();

        memset(low,0,sizeof low );

        for(int i=0;i<m;++i){

            int u,v,d,b;

            scanf("%d%d%d%d",&u,&v,&d,&b);

            low[u]-=d;

            low[v]+=d;

            net.add(u,v,b);

        }

        int ans=0;

        for(int i=1;i<=n;++i){

            if(low[i]>0) net.add(0,i,low[i]), ans+=low[i];

            if(low[i]<0) net.add(i,n+1,-low[i]);

        }

        int mf = net.max_flow(0,n+1,n+2);

        if(mf==ans)puts("happy");

        else puts("unhappy");

    }

    return 0;

}

巴特西

HDU 4940 Destroy Transportation system（无源汇有上下界最大流）

最新文章

热门文章