Description
海上有M个油田，有N个的船只和港口，N<=M，N艘船停在N个油田，油田和油田之间有距离，油田和港口之间也有距离。现在呢要你把船开回港口，每个港口只能停一艘船，问你怎么停可以使船只行驶的距离最短
Input
多组输入，每组用例第一行为四个整数N,M,K,P分别表示港口数，油田数，油田之间的边数以及油田和港口之间的边数，第二行为N个整数表示N个船只停留的油田，之后K行每行三个整数u,v,c表示u油田到v油田的距离为c，最后P行每行三个整数u,v,c表示u港口到v油田的距离为c，以文件尾结束输入
Output
对于每组用例，输出船只最短行驶距离
Sample Input
3 5 5 6
1 2 4
1 3 3
1 4 4
1 5 5
2 5 3
2 4 3
1 1 5
1 5 3
2 5 3
2 4 6
3 1 4
3 2 2
Sample Output
13
Solution
把距离当作费用，问题转化为最小费用最大流，两排点，1~M表示M个油田，M+1~M+N表示N个港口，对于有船只停留的油田，从源点到其建容量为1花费为0的边，每个港口到汇点连建容量为1花费为0的边，对于之间有道路的两个油田间建容量为无穷(路可以重复走)花费为距离的双向边，对于之间有道路的港口和油田，从油田到港口建容量为1花费为距离的单向边，建完图后用mcmf求最小费用最大流即可
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 333
#define maxm 444444
#define INF 0x3f3f3f3f
int head[maxn],d[maxn],s,e,no,dis[maxn][maxn],vis[maxn],pre[maxn];
struct point
{
int u,v,flow,next,cost;
point(){};
point(int x,int y,int z,int w,int c):u(x),v(y),next(z),flow(w),cost(c){};
}p[maxm];
void add(int x,int y,int z,int c)//建边
{
p[no]=point(x,y,head[x],z,c);
head[x]=no++;
p[no]=point(y,x,head[y],0,-c);
head[y]=no++;
}
void init()//初始化
{
memset(head,-1,sizeof(head));
no=0;
}
bool spfa()
{
int i,x,y;
queue<int>q;
memset(d,0x3f,sizeof(d));
memset(vis,false,sizeof(vis));
memset(pre,-1,sizeof(pre));
d[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty())
{
x=q.front();
q.pop();
vis[x]=false;
for(i=head[x];i!=-1;i=p[i].next)
{
if(p[i].flow&&d[y=p[i].v]>d[x]+p[i].cost)
{
d[y]=d[x]+p[i].cost;
pre[y]=i;
if(vis[y])
continue;
vis[y]=true;
q.push(y);
}
}
}
return d[e]!=d[e+1];
}
int mcmf()//最小费用最大流
{
int mincost=0,maxflow=0,minflow,i;
while(spfa())
{
minflow=INF;
for(i=pre[e];i!=-1;i=pre[p[i].u])
minflow=min(minflow,p[i].flow);
for(i=pre[e];i!=-1;i=pre[p[i].u])
{
p[i].flow-=minflow;
p[i^1].flow+=minflow;
}
mincost+=d[e]*minflow;
maxflow+=minflow;
}
return mincost;
}
int N,M,K,P;
int main()
{
while(~scanf("%d%d%d%d",&N,&M,&K,&P))
{
init();//初始化
s=0;//源点为0
e=N+M+1;//汇点为N+M+1
for(int i=1;i<=N;i++)
{
int u;
scanf("%d",&u);
add(s,u,1,0);//源点到有船只停留的油田连容量为1,花费为0的边
}
for(int i=M+1;i<=M+N;i++)//每个港口到汇点连容量为1,花费为0的边
add(i,e,1,0);
while(K--)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
//之间有道路的两个油田间建容量为无穷,花费为c的双向边
add(u,v,INF,c);
add(v,u,INF,c);
}
while(P--)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
add(v,u+M,1,c);//之间有道路的油田和港口间建容量为1,花费为c的单向边
}
printf("%d\n",mcmf());
}
return 0;
}