Mining Station on the Sea

题目大意：

                  给你n个港口和m个采矿站位于海上，有n搜船开始位于采矿站的位置，给你k条边连接两个采矿站和花费的时间，p条边连接采矿站到港口和花费的时间，问你每搜船到达港口且每个港口只能听一艘船的最少花费

题目思路：

                 我们首先考虑将港口和采矿站建立二分图，然后就是个二分图带权问题，但是采矿站之间也能走，所以我们可以用spfa预处理每个采矿站到达每个港口的最小花费，然后就可以用KM求解最小花费，这里我们可以看成是n*n的图，只要考虑有船停靠的采矿站！

AC代码：

#include<cstring>
#include<cstdio>
#include<queue>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using std::queue;
const int maxn = 1000;
const int inf= 1e8;
int n,m,k,p,e;
int hed[maxn],vis[maxn],dis[maxn],in[maxn];
queue<int>q;

struct nod{
    int v,w,nex;
}edge[maxn*maxn];

void spfa(int u){
    for(int i=1;i<=n+m;i++)dis[i]=inf;
    dis[u]=0,vis[u]=1;
    q.push(u);
    while(!q.empty()){
        u = q.front();q.pop();
        vis[u]=0;
        for(int i=hed[u];~i;i=edge[i].nex){
            int v = edge[i].v;
            if(dis[v]>dis[u]+edge[i].w){
                dis[v]=edge[i].w+dis[u];
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

void init(){
    memset(hed,-1,sizeof(hed));
    memset(vis,0,sizeof(vis));
    e=1;
}

void add(int u,int v,int w){
    edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;
}

int ex_x[maxn],ex_y[maxn],vis_x[maxn],vis_y[maxn],mp[maxn][maxn],link[maxn],slack[maxn];

void init1(){
    for(int i=1;i<=n+m;i++){
        ex_y[i]=0,ex_x[i]=-inf;
        link[i]=-1;
        for(int j=1;j<=n+m;j++){
            mp[i][j]=-inf;
        }
    }
}

bool dfs(int u){
    vis_x[u]=1;
    for(int i=m+1;i<=n+m;i++){
        if(!vis_y[i]&&mp[u][i]!=-inf){
            if(ex_x[u]+ex_y[i]==mp[u][i]){
                vis_y[i]=1;
                if(link[i]==-1||dfs(link[i])){
                    link[i]=u;
                    return true;
                }
            }else {
                slack[i]=min(slack[i],ex_x[u]+ex_y[i]-mp[u][i]);
            }
        }
    }
    return false;
}

void sove(){
    for(int i=0;i<n;i++){
        for(int j=m+1;j<=n+m;j++)slack[j]=inf;
        while(1){
            memset(vis_x,0,sizeof(vis_x));
            memset(vis_y,0,sizeof(vis_y));
            if(dfs(in[i]))break;
            int d = inf;
            for(int j=m+1;j<=n+m;j++)if(!vis_y[j])d=min(d,slack[j]);
            for(int j=1;j<=n+m;j++){
                if(vis_x[j])ex_x[j]-=d;
                if(vis_y[j])ex_y[j]+=d;
                else slack[j]-=d;
            }
        }
    }
    int res=0;
    for(int i=m+1;i<=n+m;i++){
        if(link[i]!=-1)res+=mp[link[i]][i];
    }
    printf("%d\n",-res);
}

int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&k,&p))
    {
        init();
        init1();
        for(int i=0;i<n;i++)scanf("%d",&in[i]);
        while(k--){
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        while(p--){
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            add(v,u+m,w);
        }
        for(int i=0;i<n;i++){
            int u = in[i];
            spfa(u);                  //spfa预处理
            for(int j=m+1;j<=n+m;j++){ 
                mp[u][j]=max(mp[u][j],-dis[j]);       //建立二分图
                ex_x[u]=max(ex_x[u],mp[u][j]);
            }
        }
        sove();
    }

    return 0;
}