| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 17307 | Accepted: 6687 |
Description
Input
Output
Sample Input
4 5 1 2 1 2 3 1 3 4 1 1 3 2 2 4 2
Sample Output
6
题目链接：http://poj.org/problem?id=2135
题意：有n块地，m条道路，问从1到n在返回1的最短距离，并且同一条道路不能经过2次。
思路：感觉像是先求出1-n的最短路，然后删除路径再次求最短路，但是这种方法,明显是错误的。将问题当作1-n的两条没有公共边的路径，将路径本身作为一条流量为1的路径，花费为路径长度，这样就不过是求流量为2的最小费用流
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> #include<queue> #include<stack> #include<vector> using namespace std; typedef long long ll; typedef pair<int,int> P; #define PI acos(-1.0) const int maxn=3e5+100,maxm=1e5+100,inf=0x3f3f3f3f,mod=1e9+7; const ll INF=1e18+7; struct edge { int from,to; int cap,cost; int rev; }; int n; vector<edge>G[maxn]; int h[maxn]; ///顶点的势，取h(u)=(s到u的最短距离)，边e=(u,v)的长度变成d`(e)=d(e)+h(u)-h(v)>=0 int dist[maxn]; int prevv[maxn],preve[maxn];///前驱结点和对应的边 void addedge(int u,int v,int cap,int cost) { edge e; e.from=u,e.to=v,e.cap=cap,e.cost=cost,e.rev=G[v].size(); G[u].push_back(e); e.from=v,e.to=u,e.cap=0,e.cost=-cost,e.rev=G[u].size()-1; G[v].push_back(e); } int min_cost_flow(int s,int t,int f) { int res=0; fill(h+1,h+n+1,0); while(f>0) { priority_queue<P,vector<P>,greater<P> >q; fill(dist+1,dist+n+1,inf); dist[s]=0; q.push(P(dist[s],s)); while(!q.empty()) { P p=q.top(); q.pop(); int u=p.second; if(dist[u]<p.first) continue; for(int i=0; i<G[u].size(); i++) { edge e=G[u][i]; if(e.cap>0&&dist[e.to]>dist[u]+e.cost+h[u]-h[e.to]) { dist[e.to]=dist[u]+e.cost+h[u]-h[e.to]; prevv[e.to]=u; preve[e.to]=i; q.push(P(dist[e.to],e.to)); } } } if(dist[t]==inf) return -1; for(int i=1; i<=n; i++) h[i]+=dist[i]; int d=f; for(int i=t; i!=s; i=prevv[i]) d=min(d,G[prevv[i]][preve[i]].cap); f-=d; res+=d*h[t]; for(int i=t; i!=s; i=prevv[i]) { edge &e=G[prevv[i]][preve[i]]; e.cap-=d; G[i][e.rev].cap+=d; } } return res; } int main() { int m; scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int u,v,cost; scanf("%d%d%d",&u,&v,&cost); addedge(u,v,1,cost); addedge(v,u,1,cost); } int ans=min_cost_flow(1,n,2); cout<<ans<<endl; return 0; }
原文：http://www.cnblogs.com/GeekZRF/p/7252798.html
