题意:给定一个无向图,从1走到n再从n走回1,每个边只能走一遍,求最短路
题解:可以定义一个源点s,和一个汇点t
s和1相连容量为2,费用为0,
t和n相连容量为2,费用为0
然后所用的边的容量都定为1,跑一遍最小费用最大流即可
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define MAXN 1000+10
#define INF 0x7f7f7f7f
#define ll long long
using namespace std;
struct Edge{
int from,to,cap,flow,cost;
Edge(int u=,int v=,int c=,int f=,int w=){
from=u,to=v,cap=c,flow=f,cost=w;
}
};
int n,m;
vector<Edge> edges;
vector<int> G[MAXN];
int d[MAXN];
int b[MAXN];
int a[MAXN];
int p[MAXN];
void AddEdge(int u,int v,int cap,int cost){
edges.push_back(Edge(u,v,cap,,cost));
edges.push_back(Edge(v,u,,,-cost));
int t=edges.size();
G[u].push_back(t-);
G[v].push_back(t-);
}
int SPFA(int s,int t,int &flow,ll &cost){
memset(d,0x7f,sizeof(d));
memset(b,,sizeof(b)); queue<int> q;
q.push(s);
b[s]=;
d[s]=;
a[s]=INF;
p[s]=; while(!q.empty()){
int x=q.front(); q.pop();
b[x]=;
for(int i=;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(e.cap>e.flow&&d[e.to]>d[x]+e.cost){
d[e.to]=d[x]+e.cost;
a[e.to]=min(a[x],e.cap-e.flow);
p[e.to]=G[x][i];
if(!b[e.to]){
b[e.to]=;
q.push(e.to);
}
}
}
}
if(d[t]==INF){
return ;
} flow+=a[t];
cost+=1LL*a[t]*d[t];
for(int x=t;x!=s;x=edges[p[x]].from){
edges[p[x]].flow+=a[t];
edges[p[x]^].flow-=a[t];
}
return ;
}
ll MincostMaxflow(int s,int t){
int flow=;
ll cost=;
while(SPFA(s,t,flow,cost));
return cost;
}
void solve(){
printf("%lld\n",MincostMaxflow(,n+));
}
void init(){
memset(a,,sizeof(a));
memset(p,,sizeof(p));
edges.clear();
for(int i=;i<=n;i++){
G[i].clear();
}
for(int i=;i<=m;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
u++,v++;
AddEdge(u,v,,w);
AddEdge(v,u,,w);
}
AddEdge(,,,);
AddEdge(n+,n+,,);
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
solve();
}
return ;
}