n个点的无向图,找到1->n的2条最短路,且2条路线没有重复路。
可转化成费用流模型,每条边的容量为1,限制只能选择1次,费用为路的长度,源点容量大于等于2,汇点容量大于等于2。最小费用最大流即可。
#include#include #include using namespace std; #define MAXN 5555 #define MAXM 1000000 #define INF 0x3f3f3f3f struct node { int u,v,f,c,next; }e[MAXM]; int n,k,head[MAXN],pre[MAXN],dist[MAXN],vis[MAXN]; int en,s,t,maxflow,mincost; //s源点,t汇点 void add(int u,int v,int c,int f)//加边 { e[en].u=u; e[en].v=v; e[en].c=c; e[en].f=f; e[en].next=head[u]; head[u]=en++; e[en].u=v; e[en].v=u; e[en].c=-c; e[en].f=0; e[en].next=head[v]; head[v]=en++; } int spfa() { int i,u,v; for(i=0;i<=t;i++) pre[i]=-1,vis[i]=0,dist[i]=INF; dist[s]=0; vis[s]=1; queue q; q.push(s); while(!q.empty()) { u=q.front(); q.pop(); for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(e[i].f>0&&dist[u]+e[i].c