首页 > 代码库 > 任务安排
任务安排
给定N（<=300）个人和N台机器，以及每个人操作某台机器的收益。请计算所有人都工作的情况下，最大的收益和。
输入：
第一行两个数分别表示人和机器的数量（两数相等）
接下来若干行，每行三个数，a,b,c表示a 操作机器b的收益为c.
输出：
两个数。（第一个数表示参加工作的人数（此数为N），第二个数表示最大收益和。）
样例：
输入：
3 3
1 2 10
1 1 9
1 3 3
2 1 10
2 2 9
2 3 3
3 1 8
3 2 9
3 3 8
输出：
3 28
最大费用流的话就是搞成负的再求最小费用流，也是很裸的题 。
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 const int inf = 1 << 30 , maxn = 600 + 11 ;//1061109567 7 using namespace std ; 8 int n , val[maxn][maxn] , vol[maxn][maxn] , dis[maxn] , mark[maxn] , ans , s , t ; 9 queue< int > Q; 10 11 inline void Init( ) 12 { 13 freopen( "NSOOJ#10400.in" , "r" , stdin ) ; 14 freopen( "NSOOJ#10400.out" , "w" , stdout ) ; 15 } 16 17 void add( int u , int v , int va , int vo ) 18 { 19 val[u][v] = va , vol[u][v] = vo ; 20 } 21 22 23 void input( ) 24 { 25 scanf( "%d" , &n ) ; scanf( "%d" , &n ) ; 26 int a , b ,c ; s = 0 , t = (n<<1) + 2 ; 27 while( ~scanf( "%d%d%d" , &a , &b , &c ) ) 28 { 29 // cout<<a<<" "<<b<<" "<<c<<endl; 30 add( a , b+n , inf , -c ) ; 31 add( b+n , a , 0 , c ) ; 32 } 33 for( int x = 1 ; x <= n ; ++x ) 34 { 35 add( s , x , 1 , 0 ) ; 36 add( x , s , 0 , 0 ) ; 37 } 38 for( int x = 1 ; x <= n; ++x ) 39 { 40 add( x+n , t-1 , 1 , 0 ) ; 41 add( t-1 , x+n , 0 , 0 ) ; 42 } 43 add( t-1 , t , n , 0 ) ; 44 add( t , t-1 , 0 , 0 ) ; 45 } 46 47 48 bool spfa( ) 49 { 50 memset( mark , 0 , sizeof(mark) ) ; 51 memset( dis , 127/2 , sizeof(dis) ) ; 52 mark[t] = 1 , dis[t] = 0 ; Q.push( t ) ; 53 while( !Q.empty( ) ) 54 { 55 int u = Q.front( ) ; Q.pop( ) ; 56 for( int i = 0 ; i <= t ; i++ ) 57 { 58 if( val[i][u] && dis[i] > dis[u] + vol[i][u] ) 59 { 60 dis[i] = dis[u] + vol[i][u] ; 61 if( !mark[i] ) 62 { 63 Q.push( i ) ; 64 mark[i] = true ; 65 } 66 } 67 } 68 mark[u] = false ; 69 } 70 return dis[s] != 1061109567 ; 71 } 72 73 74 int dfs( int u , int f ) 75 { 76 mark[u] = 1 ; 77 if( u == t ) return f ; 78 int w , used = 0 ; 79 for( int v = 0 ; v <= t ; ++v ) 80 { 81 if( dis[v] == dis[u] - vol[u][v] && val[u][v] && !mark[v] ) 82 { 83 w = f - used ; 84 w = dfs( v , min( w , val[u][v] ) ) ; 85 val[u][v] -= w , val[v][u] += w , used += w ; 86 ans += w * vol[u][v] ; 87 if( used == f ) return used ; 88 } 89 } 90 return used ; 91 } 92 93 94 void zkw( ) 95 { 96 int sum = 0 ; 97 while( spfa( ) ) 98 { 99 mark[t] = 1 ;100 while( mark[t] )101 {102 memset( mark , 0 , sizeof(mark) ) ;103 sum += dfs( s , inf ) ;104 }105 106 }107 printf( "%d %d\n" , sum , 0-ans ) ;108 }109 110 111 112 int main( )113 {114 // Init( ) ;115 input( ) ;116 zkw( ) ;117 // fclose( stdin ) ;118 // fclose( stdout ) ;119 return 0 ;120 }
任务安排
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。