题意:
就是从1走到n然后再走回来,一条边只能走一次,要求路径最短。
思路:
比较水,可以直接一遍费用流,不解释了,具体的看看代码,敲这个题就是为了练
练手,好久不敲了,怕比赛手生。
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 1000 + 10
#define N_edge 40000 + 20
#define INF 100000000
using namespace std;
typedef struct
{
int from ,to ,cost ,flow ,next;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int mer[N_edge];
int s_x[N_node];
void add(int a ,int b ,int c ,int d)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].flow = d;
E[tot].next = list[a];
list[a] = tot;
E[++tot].from = b;
E[tot].to = a;
E[tot].cost = -c;
E[tot].flow = 0;
E[tot].next = list[b];
list[b] = tot;
}
bool Spfa(int s ,int t ,int n)
{
int mark[N_node] = {0};
for(int i = 0 ;i <= n ;i ++) s_x[i] = INF;
mark[s] = 1 ,s_x[s] = 0;
queue<int>q;
q.push(s);
memset(mer ,255 ,sizeof(mer));
while(!q.empty())
{
int xin ,tou = q.front();
q.pop();
mark[tou] = 0;
for(int k = list[tou] ;k ;k = E[k].next)
{
xin = E[k].to;
if(s_x[xin] > s_x[tou] + E[k].cost && E[k].flow)
{
s_x[xin] = s_x[tou] + E[k].cost;
mer[xin] = k;
if(!mark[xin])
{
mark[xin] = 1;
q.push(xin);
}
}
}
}
return mer[t] != -1;
}
int M_C_Flow(int s ,int t ,int n)
{
int maxflow = 0 ,mincost = 0 ,minflow;
while(Spfa(s ,t ,n))
{
minflow = INF;
for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
if(minflow > E[i].flow) minflow = E[i].flow;
for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
{
E[i].flow -= minflow;
E[i^1].flow += minflow;
mincost += minflow * E[i].cost;
}
maxflow += minflow;
}
return mincost;
}
int main ()
{
int n ,m ,i ,a ,b ,c;
while(~scanf("%d %d" ,&n ,&m))
{
memset(list ,0 ,sizeof(list)) ,tot = 1;
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d" ,&a ,&b ,&c);
add(a ,b ,c ,1);
add(b ,a ,c ,1);
}
add(0 ,1 ,0 ,2);
add(n ,n + 1 ,0 ,2);
printf("%d
" ,M_C_Flow(0 ,n + 1 ,n + 1));
}
return 0;
}