首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。