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("NO\n");
    else
    {
        printf("YES\n");
        for(int i=0;i<m;i++)
            printf("%d\n",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;
}

相关文章

导入moment 使用方式 年月日,时分秒 星期几 相对时间 7天后 2小时后 明天 将毫秒转换成年月日
@ 一、前言 为什么介绍redux-actions呢? 第一次见到主要是接手公司原有的项目,发现有之前的大佬在处理...
十大React Hook库 原文地址:https://dev.to/bornfightcompany/top-10-react-hook-libraries-4065 原文...
React生命周期 React的生命周期从广义上分为挂载、渲染、卸载三个阶段,在React的整个生命周期中提供很...
React虚拟DOM的理解 Virtual DOM是一棵以JavaScript对象作为基础的树,每一个节点可以将其称为VNode,用...
React中JSX的理解 JSX是快速生成react元素的一种语法,实际是React.createElement(component, props, ....