题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1877
每个点只能走一次
所以拆点，跑个最小费用最大流就好了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include<bits/stdc++.h> #define inf 1000000000 #define MAXN 440 #define MAXM 100010 typedef long long ll; using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int from,to,num,cost; node(int a,int b,int c,int d){from=a,to=b,num=c,cost=d;} node(){} }edge[MAXM]; int n,m; vector<int>v[MAXN]; int edgenum=0; int dis[MAXN],pre[MAXN]; bool vis[MAXN]; void link(int x,int y,int z,int d){ edge[edgenum]=node(x,y,z,d); v[x].push_back(edgenum++); edge[edgenum]=node(y,x,0,-d); v[y].push_back(edgenum++); } bool spfa(int s,int e){ for(int i=1; i<=2*n; i++)dis[i]=inf; memset(vis,0,sizeof(vis)); dis[s]=0; vis[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int t=q.front(); q.pop(); if(t==e)continue; for(int i=0; i<v[t].size(); i++){ int x=v[t][i]; int to=edge[x].to; int num=edge[x].num; int len=edge[x].cost; if(num && dis[to]>dis[t]+len){ dis[to]=dis[t]+len; pre[to]=x; if(!vis[to])q.push(to),vis[to]=1; } } vis[t]=false; } return dis[e]!=inf; } int Maxflow=0,ans=0; void solve(int s,int e){ while(spfa(s,e)){ int Min=inf; for(int i=e; i!=s; i=edge[pre[i]].from)Min=min(Min,edge[pre[i]].num); for(int i=e; i!=s; i=edge[pre[i]].from)edge[pre[i]].num-=Min,edge[pre[i]^1].num+=Min; Maxflow+=Min; ans+=Min*dis[e]; } } int main(){ n=rd(),m=rd(); int s=1,t=n*2; for(int i=1; i<=m; i++){ int x=rd(),y=rd(),z=rd(); link(x+n,y,1,z); } for(int i=2; i<n; i++)link(i,i+n,1,0); link(1,s+n,inf,0); link(n,t,inf,0); solve(s,t); printf("%d %d\n",Maxflow,ans); return 0; } |
