学步园

/*

 题意:  一个无向图， 边的权是长度，要求从1到n， 再从n回到1的最短路长， 每条路只能走一次.

 明显是求最小环，n范围是1000，明显用floyd求最小环是不明智的,  因为从分类中知道这题是最小费用流, 所以为了不陷入这种固定思维，就很自然的往最小环和最短路，接着是最大流，发现越想越复杂， 最终还是想回费用流, 很快就想到构图了..  从起点到终点的最短路和从终点到起点的最短路是一样的，所以可以看成从源点拉两条路到汇点，所以流入汇点和流出源点的容量都是2.

构图: 长度为费用，每条边流为1， 增加源点连容量2，费用0边到1， n连汇点，容量2，费用0， 直接求最小费用

注:  wa了很久， 注意是双向边，没重边，也不会超出int

*/

#include <iostream><br /> #include <string><br /> #include <queue><br /> #include <stack><br /> using namespace std;</p> <p>#define typef int //type of flow<br /> #define typec int //type of dis</p> <p>const typef inff = 0x3f3f3f3f; //max of flow<br /> const typec infc = 0x3f3f3f3f; //max of dis<br /> const int N = 1100;<br /> const int E = 40010;</p> <p>struct network{<br /> int nv, ne, pnt[E];<br /> int nxt[E]; //next, 保存的是pnt中下标<br /> int vis[N],que[N];<br /> int head[N]; //链表头<br /> int pv[N]; //前驱节点<br /> int pe[N];<br /> typef flow,cap[E];//cap为当前流<br /> typec cost,dis[E],d[N];<br /> void addedge(int u,int v,typef c,typec w)<br /> {<br /> pnt[ne]= v;<br /> cap[ne] = c;<br /> dis[ne] =+w;<br /> nxt[ne] =head[u];<br /> head[u] =(ne++);</p> <p> pnt[ne] = u;<br /> cap[ne] = 0;<br /> dis[ne] = -w;<br /> nxt[ne] =head[v];<br /> head[v] =ne++;<br /> }<br /> typec mincost(int src,int sink) //原点和会终点<br /> {<br /> int i,k;<br /> int f,r;//队列指针，f为开头，r为结尾<br /> typef mxf;<br /> for(flow=0,cost=0;;)<br /> {<br /> memset(pv,-1,sizeof(pv));<br /> memset(vis,0,sizeof(vis));<br /> for(i=0;i<nv;i++) d[i]=infc;//球最长路时路径初始化为-1<br /> d[src] = 0;<br /> pv[src] = src;<br /> vis[src] = 1;<br /> for(f=0,r=1,que[0]=src;r!=f;)<br /> {<br /> i=que[f++];<br /> vis[i]=0;<br /> if(N==f)f=0;//循环队列<br /> for(k = head[i];k!=-1;k=nxt[k])<br /> if(cap[k]&&dis[k]+d[i]<d[pnt[k]])<br /> {<br /> d[pnt[k]]=dis[k]+d[i];<br /> if(0 == vis[pnt[k]])<br /> {<br /> vis[pnt[k]]=1;<br /> que[r++] = pnt[k];<br /> if(N == r)r=0;<br /> }<br /> pv[pnt[k]]=i;<br /> pe[pnt[k]]=k;<br /> }<br /> }<br /> if(-1 == pv[sink]) break;<br /> for(k=sink,mxf = inff;k != src;k=pv[k])<br /> if(cap[pe[k]]< mxf) mxf = cap[pe[k]];<br /> flow+= mxf;<br /> cost+=d[sink]*mxf;<br /> for(k= sink;k!=src;k=pv[k])<br /> {<br /> cap[pe[k]]-=mxf;<br /> cap[pe[k]^1]+=mxf;<br /> }<br /> }<br /> return cost;<br /> }<br /> void build()<br /> {<br /> ne = 0;<br /> memset(head,-1,sizeof(head));<br /> int x,y;<br /> typef f;<br /> typec w;<br /> int n,m,u,v,i;<br /> scanf("%d%d",&n,&m);<br /> for(i=0;i<m;i++)<br /> {<br /> scanf("%d%d%d",&x,&y,&w);<br /> addedge(x,y,1,w);<br /> addedge(y,x,1,w);<br /> }<br /> addedge(0,1,2,0);<br /> addedge(n,n+1,2,0);<br /> nv=n+2;<br /> }</p> <p>}g;</p> <p>int main()<br /> {<br /> g.build();<br /> printf("%d/n",g.mincost(0,g.nv-1));<br /> }