题目描述

题目大意：给出一张点数为 $n$，边数为 $m$ 的有向图，除了点 $1$ 和点 $n$ 外每个点和每条边只能走一次，求从点 $1$ 到点 $n$ 的最小费用最大流。

题目链接

思路

这道题主要是题面难理解。

由于一个点只能经过一次，我们一个点拆分为两个点，中间连一条流量为 $1$，费用为 $0$ 的边。

注意点 $1$ 和 点 $n$ 因为可以走不止一次，所以它们拆开的点中间的边的流量要设为无穷。

这样我们就保证了除点 $1$ 和点 $n$ 外每个点只能经过一次，然后跑一遍费用流即可。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
long long n,m,last[200005],to[200005],nextt[200005],s[200005],t[200005],top=1,ans=0,cost=0;
long long d[200005];
long long v[200005];
struct path{
    long long from,edge;
};
path p[200005];
void add(int a,int b,int c,int d){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    t[top]=d;
    last[a]=top;
}
bool spfa(long long S,long long T){
    queue<long long> q;
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    memset(p,-1,sizeof(p));
    q.push(S);
    v[S]=1;
    d[S]=0;
    d[T]=2147483647;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        for (int i=last[now];i;i=nextt[i]){
            long long j=to[i];
            if (s[i]<=0){
                continue;
            }
            if (d[now]+t[i]<d[j]){
                d[j]=d[now]+t[i];
                p[j].from=now;
                p[j].edge=i;
                if (!v[j]){
                    q.push(j);
                    v[j]=1;
                }
            }
        }
        v[now]=0;
    }
    if (d[T]<2147483647){
        return 1;
    }else{
        return 0;
    }
}
void EK(long long S,long long T){
    while (spfa(S,T)){
        long long minn=2147483647;
        for (int i=T;i!=S;i=p[i].from){
            minn=min(minn,s[p[i].edge]);
        }
        ans+=minn;
        for (int i=T;i!=S;i=p[i].from){
            s[p[i].edge]-=minn;
            s[p[i].edge^1]+=minn;
        }
        cost+=minn*d[T];
    }
}
int main(){
    cin>>n>>m;
    add(1,n+1,19260817,0);
    add(n+1,1,19260817,0);
    add(n,n*2,19260817,0);
    add(n*2,n,19260817,0);
    for (int i=1;i<=n;i++){
    	add(i,n+i,1,0);
    	add(n+i,i,0,0);
	}
    int S=1,T=n*2; 
    for (int i=1;i<=m;i++){
        int a,b,c;
        a=read();b=read();c=read();
        add(n+a,b,1,c);
        add(b,n+a,0,-c);
    }
    EK(S,T);
    cout<<ans<<" "<<cost;
}