hdu 3157 Crazy Circuits 有源汇和下界的最小费用流

题意:有n个节点，m个用电器。之后输入m行每行三个整数a,b,c;

节点a为正极(或者a 为 '+'即总的正极)，b为该用电器的负极(b = '-'表示总的负极)，c为该用电器要正常工作最小的电流；

问要使得该电路中的所有的电器都工作，总正极至少输入多大的电流?如果不存在方案，输出impossible;

思路:将下界归零后使用超级源点和汇点平衡流量，跑最大流之后，加一条题目的源点0和汇点n+1，即总正极和总负极连一条反向的容量为inf的边，再次跑最大流；

如果满足流量平衡，则添加的反向边的流量就是从总正极流出的符合要求的最小电流；

ps: 对于原理不是很懂，没能想明白；下面写下粗糙的想法；

第一次跑最大流，求出的不是从题给源点到题给汇点的流量，只是先平衡些流量。使得连边之后，再次跑最大流，从题给源点流出的流量最小；

#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef pair<int,int> PII;
#define A first
#define B second
#define MK make_pair
typedef long long ll;
typedef unsigned int uint;
int s,t,n,m;
template<typename T>
void read1(T &m)
{
    T x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){m = n+1; return ;}if(ch == '+'){m = 0;return ;} ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
    if(a>9) out(a/10);
    putchar(a%10+'0');
}
int T,kase = 1,i,j,k;
#define N 55
#define M 1000
int head[N],tot;
struct Edge{
    int from,to,cap,flow,Next;
    Edge(){}
    Edge(int f,int to,int cap,int Next):from(f),to(to),cap(cap),Next(Next),flow(0){}
}e[M<<1];
inline void ins(int u,int v,int cap)
{
    //cout<<u<<" "<<v<<" "<<cap<<endl;
    e[++tot] = Edge{u,v,cap,head[u]};
    head[u] = tot;
}
int sum[N];
int vis[N], cur[N],d[N];
queue<int> Q;
int BFS()
{
    rep1(i,0,t) vis[i] = 0;
    vis[s] = 1;d[s] = 0;
    Q.push(s);
    while(!Q.empty()){
        int u = Q.front();Q.pop();
        for(int i = head[u];i;i = e[i].Next){
            int v = e[i].to;
            if(!vis[v] && e[i].cap > e[i].flow){ // 只考虑残量网络的弧
                vis[v] = 1;
                d[v] = d[u] + 1;
                Q.push(v);
            }
        }
    }
    return vis[t];
}
int DFS(int x,int a)// a表示目前为所有弧的最小残量
{
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int& i = cur[x];i;i = e[i].Next){// 从上次考虑的弧开始
        int v = e[i].to;
        if(d[v] == d[x]+1 && (f = DFS(v,min(a,e[i].cap - e[i].flow))) > 0){
            e[i].flow += f;
            e[i^1].flow -= f;
            flow += f;
            a -= f;// 残量-流量
            if(a == 0)   break;
        }
    }
    return flow;
}
int Dinic()
{
    int flow = 0;
    while(BFS()){//在残量网络基础上不断刷新层次图;
        rep1(i,0,t) cur[i] = head[i];//记录当前探索到的点的弧的编号
        flow += DFS(s,inf);
    }
    return flow;
}
int main()
{
    //freopen("data.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&m) == 2 && n+m){
        MS0(sum);MS0(head);tot = 1;
        s = n+2, t = n + 3;
        int u,v,w;
        rep0(i,0,m){
            read3(u,v,w);
            sum[u] -= w, sum[v] += w;
            ins(u,v,inf);ins(v,u,0);
        }
        rep0(i,0,s){
            if(sum[i] > 0) ins(s,i,sum[i]),ins(i,s,0);
            if(sum[i] < 0) ins(i,t,-sum[i]),ins(t,i,0);
        }
        int flow = Dinic();
        ins(n+1,0,inf);ins(0,n+1,0);
        Dinic();
        bool flag = true;
        for(int d = head[s];d;d = e[d].Next){
            if(e[d].cap - e[d].flow){
                flag = false;
                break;
            }
        }
        for(int d = head[n+1];d;d = e[d].Next) // 是否满足流量平衡;
            if(e[d].to == 0){
                flow = e[d].flow;break;
            }
        if(!flag) puts("impossible");
        else printf("%d
",flow);
    }
    return 0;
}

hdu 3157 Crazy Circuits 有源汇和下界的最小费用流

相关推荐