HDU3488 Tour km-白红宇

HDU3488 Tour km

阅读量：6485 次

发布时间：2019-06-23

本文共 1736 字，大约阅读时间需要 5 分钟。

/* ***********************************************Author        :devilCreated Time  :2016/5/25 17:22:34************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;const int N=201;const int inf=0x3f3f3f3f;int w[N][N];int lx[N],ly[N];int link[N];int visx[N],visy[N];int slack[N];int n;bool dfs(int u){ visx[u]=1; for(int v=1;v<=n;v++) { if(visy[v]) continue; int tmp=lx[u]+ly[v]-w[u][v]; if(!tmp) { visy[v]=1; if(link[v]==-1||dfs(link[v])) { link[v]=u; return 1; } } else if(slack[v]>tmp) slack[v]=tmp; } return 0;}int km(){ memset(link,-1,sizeof(link)); memset(ly,0,sizeof(ly)); for(int i=1;i<=n;i++) { lx[i]=w[i][1]; for(int j=2;j<=n;j++) lx[i]=max(lx[i],w[i][j]); } for(int x=1;x<=n;x++) { memset(slack,inf,sizeof(slack)); while(1) { memset(visx,0,sizeof(visx)); memset(visy,0,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; if(visy[i]) ly[i]+=d; else slack[i]-=d; } } } int ans=0; for(int i=1;i<=n;i++) if(link[i]>-1) ans+=w[link[i]][i]; return ans;}int main(){ //freopen("in.txt","r",stdin); int t,m,x,y,p; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(w,-inf,sizeof(w)); while(m--) { scanf("%d%d%d",&x,&y,&p); w[x][y]=max(w[x][y],-p); } printf("%d\n",-km()); } return 0;}