不說什么，求a到b的兩條不相交路徑，使得總費用最少。你懂的。。（話說。。第一次手寫最少費用流，以前都直接Ctrl+A,Ctrl+C,Ctrl+V直接模板~）
代碼：
1 # include <cstdio>
2 # include <cstring>
3 # include <cstdlib>
4 using namespace std;
5 struct node
6 {
7 int p,c,e,s,nxt;
8 }edge[50000];
9 int g[1005],cc=0,n,m;
10 void insert(int s,int e,int c,int p)
11 {
12 edge[cc].p=p;
13 edge[cc].nxt=g[s];
14 edge[cc].e=e;
15 edge[cc].s=s;
16 edge[cc++].c=c;
17 edge[cc].p=-p;
18 edge[cc].nxt=g[e];
19 edge[cc].e=s;
20 edge[cc].s=e;
21 edge[cc++].c=0;
22 };
23 int pre[1005];
24 int min(int a,int b)
25 {
26 return a<b?a:b;
27 }
28 int callen(int s,int e)
29 {
30 int len[1005];
31 memset(len,-1,sizeof(len));
32 len[s]=0;
33 for(int i=0;i<n+2;i++)
34 for(int j=0;j<cc;j++)
35 if(edge[j].c>0&&len[edge[j].s]!=-1&&(len[edge[j].e]==-1||len[edge[j].e]>len[edge[j].s]+edge[j].p))
36 len[edge[j].e]=len[edge[j].s]+edge[j].p,pre[edge[j].e]=j;
37 return len[e];
38 }
39 int calmin(int s,int e)
40 {
41 if(e==s) return 0xfffffff;
42 else return min(calmin(s,edge[pre[e]].s),edge[pre[e]].c);
43 }
44 void adjust(int s,int e,int minnum)
45 {
46 if(e==s) return;
47 else
48 {
49 edge[pre[e]].c-=minnum;
50 edge[pre[e]^1].c+=minnum;
51 adjust(s,edge[pre[e]].s,minnum);
52 }
53 }
54 int max_flow(int s,int e)
55 {
56 int p=0;
57 while(true)
58 {
59 int len=callen(s,e);
60 if(len==-1) return p;
61 else
62 {
63 int minnum=calmin(s,e);
64 adjust(s,e,minnum);
65 p+=minnum*len;
66 }
67 }
68 }
69 int main()
70 {
71 int data[10000][3];
72 scanf("%d%d",&n,&m);
73 for(int i=0;i<m;i++)
74 scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);
75 int best=0xfffffff;
76
77 cc=0;
78 insert(0,1,2,0);
79 insert(n,n+1,2,0);
80 for(int j=0;j<m;j++)
81 insert(data[j][0],data[j][1],1,data[j][2]),insert(data[j][1],data[j][0],1,data[j][2]);
82 int p=max_flow(0,n+1);
83 best=min(best,p);
84
85 printf("%d\n",best);
86 // system("pause");
87 return 0;
88 }
89