#include "stdio.h" //poj 2135 最小费用最大流模板#include "string.h"#includeusing namespace std;#define N 1005#define INF 0x3fffffffstruct node { int u,v; int w,k; int next;}edge[4*N*10]; //题目中边的条数是N的十倍，每一条边建四次！int n,m,idx,ans;int head[N],dis[N],route[N];bool mark[N];void init(); //初始化部分变量void EK(int start,int end);int SPFA(int start,int end);void adde(int u,int v,int w,int k);void addedge(int u,int v,int w,int k);int main(){ int i; int u,v,w; while(scanf("%d%d",&n,&m)!=-1) { init(); for(i=1;i<=m;i++) { scanf("%d %d %d",&u,&v,&w); //对每一条边建两次，一正一反 adde(u,v,w,1); adde(v,u,w,1); } int start = 0; adde(start,1,0,2); //为起点添两条边，单位流量费用为0 int end = n+1; adde(n,end,0,2); //为终点添两条边,单位流量费用为0 while( SPFA(start,end) ) EK(start,end); printf("%d\n",ans); } return 0;}void init(){ ans = 0; //结果初始化 idx = 0; memset(head,-1,sizeof(head)); //}void adde(int u,int v,int w,int k) //对其中的一条再加上一条流量为0的回路{ addedge(u,v,w,k); addedge(v,u,-w,0);}void addedge(int u,int v,int w,int k) //邻接表建边{ edge[idx].u = u; edge[idx].v = v; edge[idx].w = w; edge[idx].k = k; edge[idx].next = head[u]; head[u] = idx; idx++;}int SPFA(int start,int end) //找一条存在流量的最小费用流(存在流量就行){ int i; memset(mark,false,sizeof(mark)); //初始化标记数组mark[]; memset(route,-1,sizeof(route)); //ruote[]记录流量路径(存下一条边的下标) for(i=start;i<=end;i++) dis[i] = INF; dis[start] = 0; queue q; q.push(start); mark[start] = true; int x,y; while(!q.empty()) { x = q.front(); for(i=head[x];i!=-1;i=edge[i].next) { y = edge[i].v; if(edge[i].k && dis[y] > dis[x] + edge[i].w) { dis[y] = dis[x] + edge[i].w; route[y] = i; //route[]里面存的为边的下标 if(mark[y] == false) { mark[y] = true; q.push(y); } } } q.pop(); mark[x] = false; //对出队列的点的标记还原 } if(dis[end] == INF) return 0; return 1;}void EK(int start,int end){ int x,y; y = route[end]; //对于一般的最小费用最大流，需遍历一遍route[],求出最小费用路线上能流过的最大流量k(此题恰好为1，故此步省略！) while(y!=-1) { x = y^1; //很特别的处理; edge[y].k--; //对流量进行处理(正减反加) edge[x].k++; ans += edge[y].w; y = route[edge[y].u]; //通过route[]访问路径上的下一个节点 }}