题意：有n个机器，机器之间有m条连线，我们需要判断机器0到n-1是否存在两条线路，存在输出最小费用。
思路：我们把0连接超级源点，n-1连接超级汇点，两者流量都设为2，其他流量设为1，那么只要最后我们能找到超级汇点和超级源点的流量为2就说明有两条路，输出最小值。
代码：
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
const int maxn = 1000+5;
const int maxm = 10000+5;
const int MOD = 1e7;
const int INF = 1 << 25;
using namespace std;
struct Edge{
int to,next,cap,flow,cost;
}edge[maxm];
int head[maxn],tot;
int pre[maxn],dis[maxn];
bool vis[maxn];
int N,M;
void init(){
N = maxn;
tot = 0;
memset(head,-1,sizeof(head));
}
void addEdge(int u,int v,int cap,int cost){
edge[tot].to = v;
edge[tot].cap = cap; //容量
edge[tot].flow = 0;
edge[tot].cost = cost;
edge[tot].next = head[u];
head[u] = tot++; edge[tot].to = u;
edge[tot].cap = 0;
edge[tot].flow = 0;
edge[tot].cost = -cost;
edge[tot].next = head[v];
head[v] = tot++;
}
bool spfa(int s,int t){
queue<int> q;
for(int i = 0;i < N;i++){
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost){
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
return pre[t] != -1;
}int MCMF(int s,int t,int &cost){
int flow = 0;
cost = 0;
while(spfa(s,t)){
int MIN = INF;
for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){
if(MIN > edge[i].cap - edge[i].flow){
MIN = edge[i].cap - edge[i].flow;
}
}
for(int i = pre[t];i != -1; i = pre[edge[i^1]. to]){
edge[i]. flow += MIN;
edge[i^1]. flow -= MIN;
cost += edge[i]. cost * MIN;
}
flow += MIN;
}
return flow;
}
int main(){
int n,m,Case = 1;
while(scanf("%d%d",&n,&m) && n+m){
init();
addEdge(0,1,2,0);
addEdge(n,n + 1,2,0);
int u,v,w;
while(m--){
scanf("%d%d%d",&u,&v,&w);
addEdge(u + 1,v + 1,1,w);
}
int cost;
int flow = MCMF(0,n + 1,cost);
if(flow == 2)
printf("Instance #%d: %d\n",Case++,cost);
else
printf("Instance #%d: Not possible\n",Case++);
}
return 0;
}
/*
2 1
0 1 20
2 3
0 1 20
0 1 20
1 0 10
4 6
0 1 22
1 3 11
0 2 14
2 3 26
0 3 43
0 3 58
0 0Instance #1: Not possible
Instance #2: 40
Instance #3: 73
*/
