首页 > 代码库 > hdu--3488--km<先人太聪明了>

hdu--3488--km<先人太聪明了>

2024-07-18 20:20:41   215人阅读

发明这个算法的人 太聪明了 想到了顶标这个概念 -.-

虽然 图论就是个建图过程 然后就是模板的使用 但是 一定要理解这个算法 模板 真的....

我给2个我看资料的链接..传送1 

传送2

这题的话 有一点特殊 就是需要求 相反数 因为问的是 最小值...还有 这题有重边的存在 开始WA在这里-.-

  1 #include <iostream>  2 #include <cstring>  3 #include <algorithm>  4 using namespace std;  5   6 int n;  7 const int size = 220;  8 const int inf = 0x3f3f3f3f;  9 int mp[size][size]; 10 int lx[size] , ly[size]; 11 int linker[size]; 12 bool visx[size] , visy[size]; 13 int slack[size]; 14  15 bool dfs( int x ) 16 { 17     int temp; 18     visx[x] = true; 19     for( int y = 1 ; y<=n ; y++ ) 20     { 21         if( !visy[y] ) 22         { 23             temp = lx[x] + ly[y] - mp[x][y]; 24             if( temp==0 ) 25             { 26                 visy[y] = true; 27                 if( linker[y] == -1||dfs(linker[y]) ) 28                 { 29                     linker[y] = x; 30                     return true; 31                 }     32             } 33             else if( slack[y] > temp ) 34             { 35                 slack[y] = temp;     36             } 37         } 38     } 39     return false; 40 } 41  42 void km( ) 43 { 44     int temp , ans = 0; 45     memset( ly , 0 , sizeof(ly) );//开始Y集合中顶标初始化为0 46     memset( linker , -1 , sizeof(linker) );//Y集合中某元素的边的另一端点 47     for( int i = 1 ; i<=n ; i++ ) 48     { 49         lx[i] = -inf; 50         for( int j = 1 ; j<=n ; j++ ) 51         { 52             if( mp[i][j]>lx[i] ) 53             { 54                 lx[i] = mp[i][j]; 55             } 56         } 57     } 58     for( int x = 1 ; x<=n ; x++ ) 59     { 60         for( int i = 1 ; i<=n ; i++ ) 61         { 62             slack[i] = inf; 63         } 64         while( true ) 65         { 66             memset( visx , false , sizeof(visx) ); 67             memset( visy , false , sizeof(visy) ); 68             if( dfs(x) ) 69                 break; 70             temp = inf; 71             for( int y = 1 ; y<=n ; y++ ) 72             { 73                 if( !visy[y] && temp>slack[y] ) 74                     temp = slack[y]; 75             } 76             for( int x = 1 ; x<=n ; x++ ) 77             { 78                 if( visx[x] ) 79                     lx[x] -= temp; 80             } 81             for( int y = 1 ; y<=n ; y++ ) 82             { 83                 if( visy[y] ) 84                     ly[y] += temp; 85                 else 86                     slack[y] -= temp; 87             } 88         } 89     } 90     for( int i = 1 ; i<=n ; i++ ) 91     { 92         ans += mp[ linker[i] ][i]; 93         cout << linker[i] << " " << i << endl; 94     } 95     cout << -ans << endl; 96 } 97  98 int main() 99 {100     int t , m , st , end , dist;101     while( cin>>t )102     {103         while( t-- )104         {105             memset( mp , -inf , sizeof(mp) );106             cin >> n >> m;107             while( m-- )108             {109                 cin >> st >> end >> dist;110                 mp[st][end] = mp[st][end] < -dist ? -dist : mp[st][end];111             }112             km();113         }114     }    115     return 0;116 }
View Code

这里 我想最重要的概念就是--交错树了--我还没有对KM理解地很好 不做自己想法的阐述了

 

today:

　　如果你是鱼，不要迷恋天空；如果你是鸟，不要痴情海洋。——汪国真


联系
我们