CF1766F题解

· · 题解

题意简述

解决 n\ (n\leq100) 个点， m\ (m\leq200) 条弧的 有源汇最小费用可行流 问题（不要被题目翻译误导），要求对于每条弧，容量与流量的奇偶性相同。

题目分析

注意到每条弧的流量 f 可以分为 f/2 和 f\bmod2 两部分，容量的奇偶性对于前者没有影响，而对于后者，容量为奇数会强制流量为 1, 否则强制为 0。

于是我们使用上下界网络流的方法，先强制让奇数弧流过 0.5, 再令新图的容量 c'=c/2。为了构造出可行流，根据每个点当前多流入流量的正负（如果非整数则无解），连 s\rightarrow i 或 i\rightarrow t 的费用为 -INF 的弧（这里并不需要建新的源汇点，可以直接用原图上的 s,t 连边，避免产生负环）。

之后直接在图上跑 s\rightarrow t 的最小费用流即可（注意退出条件是 dis>0，因为不需要最大流），根据是否满流判无解。记得加上奇数弧的初始流量。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>
using namespace std;

#define int long long

int n,m,x[205],y[205],c[205],w[205],dy[105],ans[205],cnt,ncnt,head[105];
int s,t,dis[105],dep[105];
queue <int> Q;

struct edge
{
    int son;
    int val;
    int fey;
    int next;
}edge[1005];

void adde(int x,int y,int p,int q)
{
    cnt++;
    edge[cnt].son=y;
    edge[cnt].val=p;
    edge[cnt].fey=q;
    edge[cnt].next=head[x];
    head[x]=cnt;
}

bool spfa()
{
    memset(dis,127,sizeof(dis));
    memset(dep,127,sizeof(dep));
    dis[s]=dep[s]=0; Q.push(s);
    while(!Q.empty())
    {
        int nr=Q.front();
        Q.pop();
        for(int i=head[nr];i>0;i=edge[i].next)
        {
            if(edge[i].val)
            {
                if(dis[nr]+edge[i].fey<dis[edge[i].son])
                {
                    dis[edge[i].son]=dis[nr]+edge[i].fey;
                    dep[edge[i].son]=dep[nr]+1;
                    Q.push(edge[i].son);
                }
            }
        }
    }
    return dis[t]<0;//注意
}
int dfs(int now,int nowflow)
{
    if(now==t) {return nowflow;}
    int nowuse=0;
    for(int i=head[now];i>0;i=edge[i].next)
    {
        if(edge[i].val&&dis[now]+edge[i].fey==dis[edge[i].son]&&dep[now]+1==dep[edge[i].son])
        {
            int flw=dfs(edge[i].son,min(edge[i].val,nowflow-nowuse));
            nowuse+=flw;
            edge[i].val-=flw;
            edge[((i-1)^1)+1].val+=flw;
        }
    }
    return nowuse;
}
void dinic()
{
    while(spfa())
    {
        int anss=dfs(1,100000000000000000);
    }
}//dinic

signed main()
{
    cin>>n>>m;
    s=1; t=n;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i]>>c[i]>>w[i];
        if(c[i]&1)
        {
            dy[x[i]]--; dy[y[i]]++;
        }
        adde(x[i],y[i],c[i]/2,w[i]);
        adde(y[i],x[i],0,-w[i]);
    }
    ncnt=cnt+1;
    for(int i=2;i<=n-1;i++)
    {
        if(dy[i]&1) {cout<<"Impossible"<<endl; return 0;}
        if(dy[i]>0) 
        {
            adde(1,i,dy[i]/2,-10000000000000000);
            adde(i,1,0,10000000000000000);
        }
        else
        {
            adde(i,n,-dy[i]/2,-10000000000000000);
            adde(n,i,0,10000000000000000);
        }
    }
    dinic();
    for(int i=ncnt;i<=cnt;i+=2)
    {
        if(edge[i].val) {cout<<"Impossible"<<endl; return 0;}
    }
    cout<<"Possible"<<endl;
    for(int i=1;i<=m;i++)
    {
        cout<<edge[i*2].val*2+c[i]%2<<" ";
    }
}