zoj 2314 Reactor Cooling (有上下界的网络流)

算法：

新建一个源点汇点 st,en，对原来的每个点i，设m(i)=流入i点的流量下限fin-流出i点的流量下限fout，若m(i)>0，连一条<s,i>容量为m(i)的边；若m(i)<0，连一条<i,t>容量为-m(i)的边。然后将原来边的容量变为c<i,j>-b<i,j>，b<i,j>为流量下届。求一次最大流。如果与s和t关联的边全部满流，则可行流存在，且每条边的流量为现在的流量+流量的下界。否则不存在可行流。

我写了一早上，用我的Dinic模板第一次过不了网络流的题（o(╯□╰)o其实我也只做过几道网络流的题啦）

Dinic算法超时，加输入优化还是TLE！

然后改EK算法，加输入优化还是TLE！无奈之下去掉输入优化试一发，诶。。。A了。。。。

纪念一下第一道有上下界的网络流！

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 210
#define maxm 40010
#define INF 0x3f3f3f3f

using namespace std;

struct node
{
    int to,v,next;
}e[maxm<<2];
int head[maxn],cnt,maxflow[maxn],flow[maxn][maxn],fin[maxn],fout[maxn];
int st,en,n,full,m,fa[maxn],l[maxm],a[maxm],b[maxm];

void add(int x,int y,int z)
{
    e[cnt].to = y;
    e[cnt].v = z;
    e[cnt].next = head[x];
    head[x] = cnt++;
    e[cnt].to = x;
    e[cnt].v = 0;
    e[cnt].next = head[y];
    head[y] = cnt++;
}
void init()
{
    memset(head,-1,sizeof(head));
    cnt = 0;
    st = 0;
    en = n+1;
    memset(fin,sizeof(fin));
    memset(fout,sizeof(fout));
    full = 0;
}
int EK()
{
    int mf = 0;
    memset(flow,sizeof(flow));
    while(1)
    {
        queue<int> q;
        memset(maxflow,sizeof(maxflow));
        maxflow[st] = INF;
        q.push(st);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i=head[u];i!=-1;i=e[i].next)
            {
                int v = e[i].to;
                if(!maxflow[v] && e[i].v>flow[u][v])
                {
                    fa[v] = u;
                    maxflow[v] = min(maxflow[u],e[i].v-flow[u][v]);
                    q.push(v);
                }
            }
        }
        if(maxflow[en]==0)
            break;
        for(int i=en;i!=st;i=fa[i])
        {
            flow[fa[i]][i]+=maxflow[en];
            flow[i][fa[i]]-=maxflow[en];
        }
        mf+=maxflow[en];
    }
    return mf;
}

void solve()
{
    int mf = EK();
    if(mf!=full)
        printf("NOn");
    else
    {
        printf("YESn");
        for(int i=0;i<m;i++)
            printf("%dn",flow[a[i]][b[i]]+l[i]);
    }
}
int main()
{
    int T,c;
    char d;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&a[i],&b[i],&l[i],&c);
            add(a[i],b[i],c-l[i]);
            fin[b[i]]+=l[i];
            fout[a[i]]+=l[i];
        }
        for(int i=1;i<=n;i++)
        {
            int tmp = fin[i]-fout[i];
            if(tmp>0)
            {
                add(st,i,tmp);
                full += tmp;
            }
            else
                add(i,-tmp);
        }
        solve();
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!