題目鏈接：點擊打開鏈接
題意：
給定n個點m條無向邊和邊權（無重邊）
找2條從1-n點路徑不相交的最短路（2條路必須都是最短）
最先是用費用流跑，結果各種mel
然後最短路優化，，，，把圖裡所有不在最短路上的邊刪掉
然後其實跑網絡流就可以了，，，開始還是mle，後來把鄰接表的from去掉才過，，
#include #include#include #include #include #include #include using namespace std; #define ll int #define N 402 #define M 121000 #define inf 10737418 #define inf64 1152921504606846976 struct Edge{ ll to, cap, nex; }edge[M*2];//注意這個一定要夠大 不然會re 還有反向弧 ll head[N], edgenum; void add(ll u, ll v, ll cap, ll rw = 0){ //如果是有向邊則：add(u,v,cap); 如果是無向邊則：add(u,v,cap,cap); Edge E = { v, cap, head[u]}; edge[ edgenum ] = E; head[u] = edgenum ++; Edge E2= { u, rw, head[v]}; edge[ edgenum ] = E2; head[v] = edgenum ++; } ll sign[N]; bool BFS(ll from, ll to){ memset(sign, -1, sizeof(sign)); sign[from] = 0; queue q; q.push(from); while( !q.empty() ){ int u = q.front(); q.pop(); for(ll i = head[u]; i!=-1; i = edge[i].nex) { ll v = edge[i].to; if(sign[v]==-1 && edge[i].cap) { sign[v] = sign[u] + 1, q.push(v); if(sign[to] != -1)return true; } } } return false; } ll Stack[N], top, cur[N]; ll Dinic(ll from, ll to){ ll ans = 0; while( BFS(from, to) ) { memcpy(cur, head, sizeof(head)); ll u = from; top = 0; while(1) { if(u == to) { ll flow = inf, loc;//loc 表示 Stack 中 cap 最小的邊 for(ll i = 0; i < top; i++) if(flow > edge[ Stack[i] ].cap) { flow = edge[Stack[i]].cap; loc = i; } for(ll i = 0; i < top; i++) { edge[ Stack[i] ].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]^1].to; } for(ll i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增廣的邊的下標 if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break; if(cur[u] != -1) { Stack[top++] = cur[u]; u = edge[ cur[u] ].to; } else { if( top == 0 )break; sign[u] = -1; u = edge[ Stack[--top]^1 ].to; } } } return ans; } void init(){memset(head,-1,sizeof head);edgenum = 0;} ll dis[N]; ll n, m; ll mp[401][401]; bool inq[N]; void spfa(int from, int to){ for(int i = 1; i <= n; i++)dis[i] = inf; memset(inq, 0, sizeof inq); dis[from] = 0; queue q; q.push(from); inq[to] = 1; while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = 0; for(int i = 1; i <= n; i++) if(dis[i]>dis[u]+mp[u][i]) { dis[i] = dis[u]+mp[u][i]; if(!inq[i])inq[i] = 1, q.push(i); } } } void dfs(ll u, ll fa){ if(u == n){printf("%d\n",u);return ;} else printf("%d ",u); for(ll i = head[u]; ~i; i = edge[i].nex){ if(edge[i^1].cap != 1 || (i&1))continue; ll v = edge[i].to; if(v == fa)continue; edge[i^1].cap = 0; dfs(v, u); return; } } int main(){ ll u, v, cost; while(~scanf("%d %d",&n,&m)){ init(); for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)mp[i][j] = inf; while(m--) { scanf("%d %d %d",&u,&v,&cost); mp[u][v] = mp[v][u] = min(mp[u][v], cost); } spfa(1,n); if(dis[n] == inf){puts("No solution");continue;} for(ll i = 1; i <= n; i++) for(ll j = 1; j <= n; j++)if(mp[i][j]!=inf && dis[j] == mp[i][j] + dis[i]) add(i,j,1); add(n,n+1,2); ll DIS = Dinic(1,n+1); if(DIS != 2){puts("No solution");continue;} else { dfs(1,1); dfs(1,1); } } return 0; } /* 4 6 1 2 1 1 3 1 2 3 1 3 4 2 2 4 1 1 4 1 3 5 1 3 1 1 3 3 1 3 3 1 2 1 2 3 1 */
