題目連結
http://www.lydsy.com/JudgeOnline/problem.php?id=1927
思路
非常好的一道最小費用最大流的題目。
題目要求在一個有邊權的有向圖中,經過所有的點,并且可以花費一定代價選擇順移,求最小代價。
這道題非常類似于最小路徑覆寫問題,但是隻是多了一個順移。在最小路徑覆寫問題中,我們把每個點拆成了入點和出點,那麼對于每個點 u 及其順移代價au而言,就從源點連容量為 au 的邊到 u <script id="MathJax-Element-43" type="math/tex">u</script>的出點即可
代碼
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXE 40000
#define MAXV 40000
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int u,v,w,cap,next;
}edges[MAXE];
int head[MAXV],nCount=;
void AddEdge(int U,int V,int W,int C)
{
edges[++nCount].u=U;
edges[nCount].v=V;
edges[nCount].w=W;
edges[nCount].cap=C;
edges[nCount].next=head[U];
head[U]=nCount;
}
void add(int U,int V,int W,int C)
{
AddEdge(U,V,W,C);
AddEdge(V,U,-W,);
}
int dist[MAXV],pre[MAXV],inQueue[MAXV],q[2*MAXE];
int S,T;
bool SPFA()
{
memset(inQueue,false,sizeof(inQueue));
memset(dist,INF,sizeof(dist));
memset(pre,-,sizeof(pre));
int h=,t=;
q[h]=S;
dist[S]=;
inQueue[S]=true;
while(h<t)
{
int u=q[h++];
inQueue[u]=false;
for(int p=head[u];p!=-;p=edges[p].next)
{
int v=edges[p].v;
if(dist[u]+edges[p].w<dist[v]&&edges[p].cap) //!!!!!!
{
dist[v]=dist[u]+edges[p].w;
pre[v]=p;
if(!inQueue[v])
{
inQueue[v]=true;
q[t++]=v;
}
}
}
}
return pre[T]!=-;
}
int MCMF()
{
int cost=;
while(SPFA())
{
int flow=INF;
for(int p=pre[T];p!=-;p=pre[edges[p].u])
flow=min(flow,edges[p].cap);
for(int p=pre[T];p!=-;p=pre[edges[p].u])
{
edges[p].cap-=flow;
edges[p^].cap+=flow;
}
cost+=flow*dist[T];
}
return cost;
}
int n,m;
inline int in(int x)
{
return x;
}
inline int out(int x)
{
return x+n;
}
int main()
{
nCount=;
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
S=MAXV-;T=MAXV-;
for(int i=;i<=n;i++)
{
int a; //順移到i的代價為a
scanf("%d",&a);
add(S,out(i),a,);
}
for(int i=;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(u>v) swap(u,v);
add(in(u),out(v),w,);
}
for(int i=;i<=n;i++)
{
add(S,in(i),,);
add(out(i),T,,);
}
printf("%d\n",MCMF());
return ;
}