首页 > 代码库 > HDU 2448 Mining Station on the Sea km

HDU 2448 Mining Station on the Sea km

 

#include<cstdio>#include<string>#include<cstring>#include<iostream>#include<map>using namespace std;const int maxn = 105;const int INF = (1<<30)-1;int g[2*maxn][2*maxn];int f[2*maxn][2*maxn];int lx[maxn],ly[maxn];int match[maxn];bool visx[maxn],visy[maxn];int slack[maxn];int a[maxn];int n,m;bool dfs(int cur){     visx[cur] = true;     for(int y=1;y<=n;y++){         if(visy[y])   continue;         int t=lx[cur]+ly[y]-g[cur][y];         if(t==0){            visy[y] = true;            if(match[y]==-1||dfs(match[y])){                match[y] = cur;                return true;            }         }         else if(slack[y]>t){                 slack[y]=t;         }     }     return false;}int KM(){    memset(match,-1,sizeof(match));    memset(ly,0,sizeof(ly));    for(int i=1 ;i<=n;i++){         lx[i]=-INF;       for(int j=1;j<=n;j++)           if(g[i][j]>lx[i])   lx[i]=g[i][j];    }    for(int x=1;x<=n;x++){        for(int i=1;i<=n;i++)  slack[i]=INF;        while(true){            memset(visx,false,sizeof(visx));            memset(visy,false,sizeof(visy));            if(dfs(x))  break;            int d=INF;            for(int i=1;i<=n;i++){               if(!visy[i]&&d>slack[i])     d=slack[i];            }            for(int i=1;i<=n;i++){               if(visx[i])                  lx[i]-=d;            }            for(int i=1;i<=n;i++){               if(visy[i])                 ly[i]+=d;               else                        slack[i]-=d;            }        }   }    int result = 0;    for(int i = 1; i <=n ; i++){      if(match[i]>-1){        result += g[match[i]][i];      }    }    return result;}int main(){    int val,k,p;    int x,y,d;    while(scanf("%d%d%d%d",&n,&m,&k,&p)!=EOF){        for(int i=1;i<=n;i++)  scanf("%d",&a[i]);        memset(f,-1,sizeof(f));        for(int i=0;i<k;i++){            scanf("%d%d%d",&x,&y,&d);            f[x][y]=f[y][x]=d;        }        for(int i=1;i<=m;i++) f[i][i]=0;        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=INF;        for(int k=1;k<=m;k++)           for(int i=1;i<=m;i++)            for(int j=1;j<=m;j++){                if(f[i][k]!=-1&&f[k][j]!=-1){                    int t=f[i][k]+f[k][j];                    if(f[i][j]==-1||f[i][j]>t){                       f[i][j]=t;                    }                }            }            for(int i=0;i<p;i++){                scanf("%d%d%d",&x,&y,&d);                for(int j=1;j<=n;j++){                    int t=(d+f[y][a[j]]);                   if(t<g[x][j])                    g[x][j]=t;                }            }            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)               g[i][j]=-g[i][j];        int ans=-KM();        printf("%d\n",ans);    }    return 0;}