P2153晨跑

最小费用流模板

注意十字路口只能过一次，所以需要对每个点进行拆点

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
#include<queue>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[M], ret;
bool vis[N];

void add(int u, int v, int w, int c)
{
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}

void addedge(int u,int v,int w,int c){
    add(u,v,w,c);
    add(v,u,0,-c);
}

bool spfa(int s,int t){
    memset(dis,0x3f,sizeof(dis));
    memcpy(cur,lnk,sizeof(lnk));
    queue<int >q ;
    q.push(s),dis[s]=0,vis[0]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop(),vis[u]=0;
        for(int i=lnk[u];i;i=nxt[i]){
            int v=ter[i];
            if(cap[i]&&dis[v]>dis[u]+cost[i]){
                dis[v]=dis[u]+cost[i];
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
    return dis[t]!=INF;
}

int dfs(int u,int t,int flow){
    if(u==t)return flow;
    vis[u]=1;
    int ans=0;
    for(int &i=cur[u];i&&ans<flow;i=nxt[i]){
        int v=ter[i];
        if(!vis[v]&&cap[i]&&dis[v]==dis[u]+cost[i]){
            int x=dfs(v,t,min(cap[i],flow-ans));
            if(x)ret+=x*cost[i],cap[i]-=x,cap[i^1]+=x,ans+=x;
        }
    }
    vis[u]=0;
    return ans; 
}


int mcmf(int s,int t){
    int ans=0;
    while(spfa(s,t)){
        int x;
        while((x=dfs(s,t,INF)))ans+=x;
    }
    return ans;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    f(i,1,n-1){
        addedge(i,i+n,1,0);
    }
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        addedge(a+n,b,1,c);
    }
    int ans=mcmf(1+n,n);
    cout<<ans<<" "<<ret;
    return 0;
}