首页 > 代码库 > POJ3155 Hard Life
POJ3155 Hard Life
| Time Limit: 8000MS | Memory Limit: 65536K | |
| Total Submissions: 8482 | Accepted: 2461 | |
| Case Time Limit: 2000MS | Special Judge |
Description
John is a Chief Executive Officer at a privately owned medium size company. The owner of the company has decided to make his son Scott a manager in the company. John fears that the owner will ultimately give CEO position to Scott if he does well on his new manager position, so he decided to make Scott’s life as hard as possible by carefully selecting the team he is going to manage in the company.
John knows which pairs of his people work poorly in the same team. John introduced a hardness factor of a team — it is a number of pairs of people from this team who work poorly in the same team divided by the total number of people in the team. The larger is the hardness factor, the harder is this team to manage. John wants to find a group of people in the company that are hardest to manage and make it Scott’s team. Please, help him.
In the example on the picture the hardest team consists of people 1, 2, 4, and 5. Among 4 of them 5 pairs work poorly in the same team, thus hardness factor is equal to 5⁄4. If we add person number 3 to the team then hardness factor decreases to 6⁄5.
Input
The first line of the input file contains two integer numbers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Here n is a total number of people in the company (people are numbered from 1 to n), and m is the number of pairs of people who work poorly in the same team. Next m lines describe those pairs with two integer numbers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) on a line. The order of people in a pair is arbitrary and no pair is listed twice.
Output
Write to the output file an integer number k (1 ≤ k ≤ n) — the number of people in the hardest team, followed by k lines listing people from this team in ascending order. If there are multiple teams with the same hardness factor then write any one.
Sample Input
sample input #15 61 55 44 22 51 23 1sample input #24 0
Sample Output
sample output #141245sample output #211
Hint
Note, that in the last example any team has hardness factor of zero, and any non-empty list of people is a valid answer.
Source
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <queue> 6 #include <cmath> 7 const double eqs = 1e-8 ; 8 const int N = 100 + 11 , M = 1000 + 11 ; 9 using namespace std ; 10 int n , m , head[N] , cnt , s , t , du[N] , num , cur[N] , node[N] ; 11 struct ide 12 { 13 int u , v ; 14 } edge[M] ; 15 struct id 16 { 17 int fro ,nxt , to ; double w ; 18 } links[140000] ; 19 20 void add( int u , int v , double val ) 21 { 22 links[++cnt].fro = u , links[cnt].to = v ; 23 links[cnt].nxt = head[u] , links[cnt].w = val , head[u] = cnt ; 24 } 25 26 27 void Init( ) 28 { 29 scanf( "%d%d" , &n , &m ) ; s = 0 , t = n + 1 ; 30 for( int x = 1 ; x <= m ; ++x ) 31 { 32 scanf( "%d%d" , &edge[x].u , &edge[x].v ) ; 33 ++du[edge[x].u] , ++du[edge[x].v] ; 34 } 35 } 36 37 int dis[N] ; queue< int > Q ; 38 bool bfs( ) 39 { 40 memset( dis , -1 , sizeof(dis) ) ; 41 dis[s] = 0 ; Q.push( s ) ; 42 while( !Q.empty( ) ) 43 { 44 int u = Q.front( ) ; Q.pop( ) ; 45 for( int i = head[u] ; ~i ; i = links[i].nxt ) 46 { 47 int v = links[i].to ; 48 if( dis[v] < 0 && fabs( links[i].w ) > eqs ) 49 { 50 dis[v] = dis[u] + 1 ; 51 Q.push( v ) ; 52 } 53 } 54 } 55 return dis[t] != -1 ; 56 } 57 58 59 double dfs( int u , double f ) 60 { 61 if( u == t ) return f ; 62 double an , cost = 0.00 ; 63 for( int i = cur[u] ; ~i ; i = links[i].nxt ) 64 { 65 int v = links[i].to ; 66 if( dis[v] != dis[u] + 1 ) continue ; 67 an = dfs( v , min( f - cost , links[i].w ) ) ; 68 cost += an ; links[i^1].w += an , links[i].w -= an ; 69 if( fabs( links[i].w ) > eqs ) cur[u] = i ; 70 if( fabs( cost - f ) < eqs ) return cost ; 71 } 72 if( fabs( cost ) < eqs ) dis[u] = -1 ; 73 return cost ; 74 } 75 76 double Dinic( ) 77 { 78 double ans = 0.00 ; 79 while( bfs( ) ) 80 { 81 for( int x = s ; x <= t ; ++x ) cur[x] = head[x] ; 82 ans += dfs( s , 20000011 ) ; 83 } 84 //cout<<ans<<endl; 85 return ans ; 86 } 87 88 89 double check( double mid ) 90 { 91 //cout<<mid<<endl; 92 cnt = -1 ; memset( head , -1 , sizeof(head) ) ; 93 for( int i = 1 ; i <= n ; ++i ) 94 { add( s , i , m*1.0 ) , add( i , s , 0 ) ; 95 add( i , t , m + 2 * mid - du[i] ) ; 96 add( t , i , 0 ) ; 97 } 98 for( int i = 1 ; i <= m ; ++i ) 99 {100 add( edge[i].u , edge[i].v , 1.0 ) ; 101 add( edge[i].v , edge[i].u , 0.0 ) ; 102 add( edge[i].v , edge[i].u , 1.0 ) ; 103 add( edge[i].u , edge[i].v , 0.0 ) ; 104 }105 return Dinic( ) ;106 }107 108 bool vis[N] ;109 void flow( int u )110 { 111 vis[u] = true ;112 if( u >= 1 && u <= n ) node[++num] = u ;113 for( int i = head[u] ; ~i ; i = links[i].nxt )114 if( links[i].w > 0 && !vis[links[i].to] ) flow( links[i].to ) ; 115 }116 117 118 void Solve( )119 {120 double l = 0 , r = m , minn = 1.00 / n / n ;//cout<<l<<" "<<r<<endl;121 while( r - l >= minn )122 {123 double mid = ( r + l ) / 2 ;124 double hg = check( mid ) ; //cout<<l<<" "<<hg<<endl ;125 if( ( m * n - hg )* 0.5 > eqs ) l = mid ;126 else r = mid ;127 128 }129 130 check( l ) ; num = 0 ; 131 flow( s ) ; if( num == 0 ) node[++num] = 1 ;132 sort( node + 1 , node + 1 + num ) ;133 printf( "%d\n" , num ) ;134 for( int x = 1 ; x <= num ; ++x ) printf( "%d\n" , node[x] ) ;135 }136 137 138 int main( )139 {140 // freopen( "poj3155.in" , "r" , stdin ) ;141 // freopen( "poj3155.out" , "w" , stdout ) ;142 Init( ) ;143 Solve( ) ;144 // fclose( stdin ) ;145 // fclose( stdout ) ;146 return 0 ;147 }
POJ3155 Hard Life