學到了拆點法，很奇妙很厲害

#include<iostream> #include<string.h> #include<vector> #include<stdio.h> #include<queue> using namespace std; const int INF=0x7fffffff; const int maxn=2010; struct Edge {int from,to,cap,flow,cost;Edge(int u,int v,int f,int c,int co):from(u),to(v),flow(f),cap(c),cost(co){}; }; int n,bian,m; vector<Edge> edges; vector<int> num[maxn]; int a[maxn],p[maxn],d[maxn]; bool visit[maxn]; void add(int u,int v,int cap,int cost) {edges.push_back(Edge(u,v,0,cap,cost));edges.push_back(Edge(v,u,0,0,-cost));m+=2;num[u].push_back(m-2);num[v].push_back(m-1); } void bellman(int s,int t,long long &cost) {int i,x;while(true){for(i=1;i<=(n<<1);i++) d[i]=INF;memset(visit,0,sizeof(false));queue<int> q;q.push(s);p[s]=0,a[s]=INF,d[s]=0,visit[s]=true;while(!q.empty()){x=q.front(),q.pop(),visit[x]=false;for(i=0;i<num[x].size();i++){Edge &e=edges[num[x][i]];if(e.cap>e.flow&&d[e.to]>d[x]+e.cost){a[e.to]=min(a[x],e.cap-e.flow);p[e.to]=num[x][i];d[e.to]=d[x]+e.cost;if(!visit[e.to]){visit[e.to]=true;q.push(e.to);}}}}if(d[t]==INF) return ;for(i=t;i!=s;i=edges[p[i]].from){edges[p[i]].flow+=a[t];edges[p[i]^1].flow-=a[t];}cost+=(long long)d[t]*(long long)a[t];} } int main() {int i,from,to,cost;while(scanf("%d%d",&n,&bian)!=EOF){edges.clear();for(i=1;i<=(n<<1);i++) num[i].clear();m=0;add(1,n+1,2,0);add(n,n<<1,2,0);for(i=2;i<n;i++) add(i,i+n,1,0);for(i=1;i<=bian;i++){scanf("%d%d%d",&from,&to,&cost);add(from+n,to,1,cost);}long long cost=0;bellman(1,n<<1,cost);printf("%lld\n",cost);}return 0; }

總結

以上是生活随笔為你收集整理的UVA1658的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。