Problem A : Network Wars
提交网址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2676
参考程序：
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std ;
typedef long long lld ;
const lld INF = (lld)1<<60 ;
const double EPS = 1e-5 ;
const lld VALUE = 1000000;
const lld maxn = 110 ;
struct node
{
lld x , y , c , next ;
};
node e[maxn*maxn] ;
lld es , hd[maxn] ;
lld Vcnt , Ecnt , S , T ;
lld gh[maxn][maxn] ;
inline int sgn(double x){
return (x>EPS) - (x<-EPS) ;
}
void ins(lld x , lld y , lld c){
e[es].x = x , e[es].y = y ,e[es].c = c , e[es].next = hd[x] , hd[x] = es ++ ;
e[es].x = y , e[es].y = x ,e[es].c = 0 , e[es].next = hd[y] , hd[y] = es ++ ;
}
lld dep[maxn] , ps[maxn] , cur[maxn] ;
lld MaxFlow(){
lld tr , x ,y ,i , j ,k , f ,r , top , maxf = 0 ;
while(1){
memset(dep , -1 ,sizeof(dep)) ; dep[S] = 0 ; f = r = 0 ; ps[r++] = S ;
while(f!=r){
x = ps[f++] ;
for(i = hd[x] ; i!=-1 ; i=e[i].next)
if(e[i].c && dep[y = e[i].y] == -1)
ps[r++] = y , dep[y] = dep[x] + 1 ;
if(dep[T]!=-1) break;
}
if(dep[T] == -1) break ;
i = S , top = 0 ; memcpy(cur ,hd ,sizeof(hd));
while(1){
if(i == T){
for(tr = INF , k = 0 ; k < top ; ++ k)
if(e[ps[k]].c < tr) tr = e[ps[f = k]].c ;
for(k = 0 ; k < top ; ++ k)
e[ps[k]].c -= tr ,e[ps[k]^1].c += tr ;
maxf += tr , i = e[ps[top = f]].x ;
}
for(j = cur[i] ; j!=-1 ; j = cur[i] = e[j].next)
if(e[j].c && dep[e[j].y] == dep[i] + 1) break ;
if(j!=-1){
ps[top++] = j ; i = e[j].y ;
}else{
if(top == 0 ) break ;
dep[i] = -1 ; i = e[ps[--top]].x ;
}
}
// cout<<maxf<<endl;
// cout<<"LOOP"<<endl;
}
return maxf ;
}
int mark[maxn][maxn];
lld build(double k){
lld i , j , w , add = 0;
es = 0 ; memset(hd , -1 ,sizeof(hd)) ; S = 1 ; T = Vcnt ;
memset(mark , 0 ,sizeof(mark));
for(i = 1 ; i <= Vcnt ; ++ i)
for(j = 1 ; j < i ; ++ j )
if(gh[i][j]!=-1){
w = gh[i][j] * VALUE - (lld)(k*(double)VALUE) ;
if(w > 0 ){
ins(i , j , w);
ins(j , i , w);
}else{
add += w ; mark[i][j] = mark[j][i] = 1 ;
}
}
return add ;
}
double OK(double k){
lld ans = build(k) ;
return (double)(ans + MaxFlow()) / (double)VALUE;
}
int vis[maxn];
void dfs(lld x){
lld i , y ;
vis[x] = 1 ;
for(i = hd[x] ; i!=-1 ;i=e[i].next){
y = e[i].y;
if(!vis[y] && e[i].c){
dfs(y);
}
}
}
int main(){
lld i , j , k ,sum , x ,y , w ,tot , testCase = 1;
double l , r , mid , tr ;
lld st[405] ,ed[405] ;
while(scanf("%lld%lld" ,&Vcnt ,&Ecnt)!=EOF){
if(testCase != 1) printf("\n"); testCase ++ ;
sum = 0 ;
for(i = 1 ; i <= Vcnt ;++ i) for(j = 1 ; j <= Vcnt ;++j) gh[i][j] = -1;
for(i = 1 ; i <= Ecnt ; ++ i){
scanf("%lld%lld%lld" ,&x,&y,&w);
if(x > y) swap(x ,y);
st[i] = x , ed[i] = y;
gh[x][y] = gh[y][x] = w ;
sum += w ;
}
l = 1/(double)Ecnt ; r = (double)sum ;
while(sgn(l - r)){
mid = (l + r) / 2 ;
tr = OK(mid) ;
if(sgn(tr) == 0) break ;
if(sgn(tr)== -1){
r = mid ;
}else{
l = mid ;
}
//cout<<"While Loop"<<endl;
}
//cout<<"Answer : " << l <<endl;
build(r); MaxFlow();
memset(vis , 0 , sizeof(vis)) ;
dfs(S) ;
for(i = 1 ; i<=Vcnt ;++i)
if(vis[i]){
for(k = hd[i] ; k !=-1 ; k = e[k].next)
if(!vis[j = e[k].y])
mark[i][j] = mark[j][i] = 1 ;
}
tot = 0 ;
for(i = 1 ; i<=Vcnt ;++i)
for(j = 1 ; j<i; ++j)
if(mark[i][j]) ++ tot;
printf("%lld\n" ,tot);
int ct = 1 ;
for(i = 1 ; i <=Vcnt ;++i)
for(j = 1 ; j <i; ++j)
if(mark[i][j]){
for(k = 1 ; k <= Ecnt ; ++ k)
if(i == ed[k] && j == st[k]) break ;
if(ct == 1)
printf("%lld" , k);
else
printf(" %lld" , k);
++ ct ;
}
printf("\n");
}
return 0 ;
}
Problem B : Optimal Marks
提交网址：http://www.spoj.pl/problems/OPTM/
参考程序：
#include<iostream>
#include<string.h>
using namespace std ;
const int maxV = 505 ;
const int maxE = 3005 * 10 ;
const int INF = 2000000000;
const int FLOWINF = maxE ;
struct node{
int x , y , c ,next ;
};
node e[maxE] ;
int N , Vcnt , Ecnt , S ,T , es , hd[maxV];
int st[maxE] ,ed[maxE] , mark[maxV] , newMark[maxV];
inline int BIT(int x , int i){
return (1<<i)&x ? 1 : 0 ;
}
inline void ins(int x, int y ,int c){
e[es].x = x ,e[es].y = y ,e[es].c = c , e[es].next = hd[x] , hd[x] = es ++ ;
e[es].x = y ,e[es].y = x ,e[es].c = 0 , e[es].next = hd[y] , hd[y] = es ++ ;
}
void input(){
int i , j , x , y , K ;
scanf("%d%d" , &Vcnt ,&Ecnt);
for(i = 1 ; i <= Ecnt ; ++i) scanf("%d%d" ,&st[i] ,&ed[i]);
scanf("%d" ,&K); memset(mark , -1 ,sizeof(mark));
for(i = 1 ; i <= K ; ++i){
scanf("%d%d" , &x ,&y); mark[x] = y ;
}
}
int dep[maxV] , ps[maxV] , cur[maxV] ;
int MaxFlow(){
int f , r , i , j , k , x , y , top , tr ,maxf = 0 ;
while(1){
memset(dep , -1 ,sizeof(dep)); dep[S] = 0 ; f = r = 0 ; ps[r++] = S ;
while(f!=r){
x = ps[f++] ;
for(i = hd[x] ; i!=-1 ; i=e[i].next)
if(e[i].c && dep[y=e[i].y] == -1)
ps[r++] = y , dep[y] = dep[x] + 1 ;
if(dep[T] != -1) break ;
//cout<<"LOOP"<<endl ;
}
if(dep[T]==-1) break ;
i = S ,top = 0 ; memcpy(cur ,hd ,sizeof(hd));
while(1){
if(i==T){
for(tr = INF , k = 0 ; k <top ; ++ k)
if(e[ps[k]].c < tr) tr = e[ps[f = k]].c ;
for(k = 0 ; k < top ; ++ k)
e[ps[k]].c -= tr , e[ps[k]^1].c +=tr ;
maxf += tr , i = e[ps[top=f]].x ;
}
for(j = cur[i] ; j!=-1 ; j=cur[i]=e[j].next)
if(e[j].c && dep[e[j].y] == dep[i] + 1) break ;
if(j!=-1){
ps[top++] = j , i = e[j].y ;
}else{
if(0==top) break ;
dep[i]=-1 ; i = e[ps[--top]].x ;
}
// cout<<"LOOP"<<endl;
}
// cout<<"LOOP"<<endl;
}
return maxf;
}
int vis[maxV] ;
void dfs(int x){
int i , y ;
vis[x] = 1 ;
for(i = hd[x] ;i!=-1 ; i=e[i].next){
y = e[i].y ;
if(!vis[y] && e[i].c) dfs(y);
}
// cout<<"LOOP"<<endl;
}
void work(){
int b , i , j , k , flag = 0;
memset(newMark , 0 ,sizeof(newMark));
for(b = 0 ; b < 32 ; ++ b){
memset(hd , -1 ,sizeof(hd)); //flag = 0 ;
es = 0 ; S = Vcnt + 1 ; T = Vcnt + 2 ; N = Vcnt + 2 ;
for(k = 1 ; k <= Vcnt ;++k)
if(mark[k]!=-1 ){
flag = 1 ;
if(BIT(mark[k],b)==1)
ins(S , k , FLOWINF);
else
ins(k , T , FLOWINF);
}
//if(flag == 0 ) break ;
for(k = 1 ; k <=Ecnt ; ++k) {
ins(st[k] , ed[k] , 1);
ins(ed[k] , st[k] , 1);
}
int maxf = MaxFlow(); /**//**//**//**//**//**//**//// cout<<"maxf = :"<<maxf<<endl;
memset(vis ,0 , sizeof(vis)); dfs(S);
for(i = 1 ; i <= Vcnt ;++i)
if(vis[i] == 1)
newMark[i]|= 1<<b ;
}
for(i = 1 ; i <= Vcnt ;++i)
printf("%d\n" , mark[i]!=-1 ? mark[i] : newMark[i]);
}
int main(){
int testCase ;
scanf("%d" , &testCase);
while(testCase--){
input();
work();
}
//while(getchar());
return 0 ;
}
Problem C : 最大获利 Profit
提交网站：http://www.rqnoj.cn/Problem_556.html
参考程序：
#include<iostream>
using namespace std ;
const int maxn = 5005 ;
const int maxm = 50005;
const int maxV = maxn + maxm + 2 ;
const int maxE = 2*(maxn + maxm + 2*maxm+1) ;
const int INF = 200000000 ;
struct node{
int x , y , c, next ;
};
node e[maxE] ;
int es , hd[maxV] , S , T , n , m ;
void ins(int x, int y ,int c){
e[es].x = x ,e[es].y = y ,e[es].c = c ,e[es].next = hd[x] , hd[x] = es ++ ;
e[es].x = y ,e[es].y = x ,e[es].c = 0 ,e[es].next = hd[y] , hd[y] = es ++ ;
}
int dep[maxV] , cur[maxV] , ps[maxV] ;
int MaxFlow(){
int i , j , k , x , y , tr , maxf = 0 , f , r , top ;
while(1){
memset(dep , -1 ,sizeof(dep)); dep[S] = 0 ; f = r = 0 ; ps[r++] = S ;
while(f!=r && dep[T] == -1){
for(i = hd[x = ps[f++]] ; i!=-1 ; i=e[i].next)
if(e[i].c && dep[y = e[i].y] == -1)
ps[r++] = y , dep[y] = dep[x] + 1 ;
}
if(dep[T]==-1) break ;
i = S , top = 0 ; memcpy(cur , hd ,sizeof(hd));
while(1){
if(i == T){
for(tr = INF , k = 0 ; k < top ; ++ k)
if(e[ps[k]].c < tr) tr = e[ps[f = k]].c ;
for(k = 0 ; k < top ; ++ k)
e[ps[k]].c -= tr ,e[ps[k]^1].c += tr ;
maxf += tr , i = e[ps[top = f]].x ;
}
for(j = cur[i] ; j!=-1 ; j = cur[i] = e[j].next)
if(e[j].c && dep[e[j].y] == dep[i] + 1) break ;
if(j!=-1){
ps[top++] = j ; i = e[j].y ;
}else{
if(0 == top ) break ;
dep[i] = -1 ; i = e[ps[--top]].x ;
}//cout<<"LOOP"<<endl;
}
}
return maxf ;
}
int main(){
int i ,x ,y , w ,sum = 0 ;
scanf("%d%d" ,&n , &m);
es = 0 ; memset(hd , -1 ,sizeof(hd)); S = n + m + 1 ; T = n + m + 2 ;
for(i = 1 ; i<=n ; ++i){
scanf("%d" ,&w);
ins(m + i , T , w );
}
for(i = 1 ; i<=m ; ++i){
scanf("%d%d%d" ,&x ,&y ,&w);
sum += w ;
ins(S , i , w );
ins(i , m + x , INF);
ins(i , m + y , INF);
}
printf("%d\n" , sum - MaxFlow());
//while(getchar());
return 0 ;
}
Problem D ：Hard Life
提交网站：http://poj.org/problem?id=3155
参考程序_1 :
#include<iostream>
using namespace std ;
typedef __int64 lld ;
const int maxn = 110 ;
const int maxe = 5000 ;
const double EPS = 1e-5 ;
const double MULTIPLE = 1000000000 ;
const lld LLD_INF = (lld)1<<60 ;
int n , m , st[1005] , ed[1005] , vis[maxn] , dgr[maxn] ;
struct node{
int x , y , next ;
lld c ;
};
node e[maxe] ;
int es , hd[maxn] , S , T ;
void ins(int x , int y , double c){
e[es].x = x ,e[es].y = y ,e[es].c = (lld)(c*MULTIPLE) , e[es].next = hd[x] , hd[x] = es ++ ;
e[es].x = y ,e[es].y = x ,e[es].c = 0 , e[es].next = hd[y] , hd[y] = es ++ ;
}
int dep[maxn] , ps[maxn] , cur[maxn] ;
double MaxFlow(){
int i , j , k , x ,y , top , f, r ;
lld tr , maxf = 0 ;
while(1){
memset(dep , -1 ,sizeof(dep)); dep[S] = 0 ; f = r = 0 ; ps[r++] = S ;
while(f!=r && dep[T]==-1){
for(i = hd[x = ps[f++]] ; i!=-1 ; i=e[i].next)
if(e[i].c && dep[y = e[i].y] == -1) ps[r++] = y , dep[y] = dep[x] + 1 ;
}
if(dep[T] == -1) break ;
i = S , top = 0 ; memcpy(cur , hd ,sizeof(hd));
while(1){
if(i == T){
for(tr = LLD_INF , k = 0 ; k < top ; ++ k)
if(e[ps[k]].c < tr ) tr = e[ps[f=k]].c ;
for(k = 0 ; k < top ; ++ k)
e[ps[k]].c -= tr , e[ps[k]^1].c +=tr ;
maxf += tr , i = e[ps[top=f]].x ;
}
for(j = cur[i] ;j!=-1 ; j=cur[i]=e[j].next)
if(e[j].c && dep[e[j].y] == dep[i] + 1) break ;
if(j!=-1){
ps[top++] = j ; i =e[j].y ;
}else{
if(top==0) break ;
dep[i]=-1 ; i =e[ps[--top]].x ;
}
}
}
return double(maxf)/MULTIPLE ;
}
double calc(double g){
int i , j ;
es = 0 ; memset(hd , -1 ,sizeof(hd)) ; S = n + 1 ; T = n + 2 ;
for(i = 1 ; i <= m ; ++i){
ins(st[i] , ed[i] , 1.0);
ins(ed[i] , st[i] , 1.0);
}
for(i = 1 ; i <= n ; ++i){
ins(S , i , m);
ins(i , T , m + 2*g - dgr[i]);
}
return (m*n - MaxFlow())/2.0 ;
}
void dfs(int x){
int i ,y ;
vis[x] = 1 ;
for(i = hd[x] ; i!=-1 ; i=e[i].next)
if(e[i].c && !vis[y=e[i].y])
dfs(y);
}
void work(){
double sol , l = 0 , r = m , mid ;
while(l + EPS < r){
mid = (l + r) /2.0 ;
if(calc(mid) > EPS)
l = mid ;
else
r = mid ;
}
calc(l);
//cout<<"Answer : "<< l <<endl;
memset(vis , 0 ,sizeof(vis)); dfs(S);
int cnt = 0 , i ;
for(i = 1 ; i<= n ; ++i)
if(vis[i])
++ cnt;
printf("%d\n" , cnt);
for(i = 1 ; i<= n ; ++i)
if(vis[i])
printf("%d\n",i);
}
int main(){
int i , j ;
while(scanf("%d%d" ,&n , &m)!=EOF){
memset(dgr , 0 ,sizeof(dgr));
for(i = 1 ; i <= m ; ++i){
scanf("%d%d" , &st[i] , &ed[i]);
dgr[st[i]] ++ ; dgr[ed[i]] ++ ;
}
if(m==0){
printf("1\n1\n");
}else{
work();
}
}
return 0 ;
}
参考程序_2 :
#include<iostream>
using namespace std ;
const int maxn = 110 ;
const int maxe = 1005 * 5;
const double DOUBLE_INF = 1e300 ;
const double EPS0 = 1e-5 ;
const double EPS = 1e-18 ;
int n ,m , st[maxe] , ed[maxe] ,dgr[maxn];
struct node{
int x , y , next ;
double c ;
};
node e[maxe] ;
int es ,hd[maxn] , S , T ;
inline int sgn(double x){
return (x>EPS0)-(x<-EPS0) ;
}
void ins(int x ,int y ,double c){
e[es].x = x ,e[es].y = y ,e[es].c = c , e[es].next = hd[x] , hd[x] = es ++ ;
e[es].x = y ,e[es].y = x ,e[es].c = 0 , e[es].next = hd[y] , hd[y] = es ++ ;
}
int dep[maxn] , ps[maxn] , cur[maxn] ;
double MaxFlow(){
int i ,j , k , x ,y , top , f , r ;
double tr , maxf = 0.0 ;
while(1){
memset(dep , -1 ,sizeof(dep)); dep[S] = 0 ; f = r = 0 ; ps[r++] = S ;
while( f!=r && dep[T] == -1){
for(i = hd[x = ps[f++]] ; i!=-1 ; i=e[i].next)
if(e[i].c > EPS && dep[y = e[i].y] == -1)
ps[r++] = y , dep[y] = dep[x] + 1 ;
}
if(dep[T]==-1) break;
i = S , top = 0 ; memcpy(cur , hd ,sizeof(hd));
while(1){
if(i == T){
for(tr = DOUBLE_INF , k = 0 ; k < top ; ++ k)
if(e[ps[k]].c < tr ) tr = e[ps[f=k]].c ;
for(k = 0 ; k < top ; ++ k)
e[ps[k]].c -= tr , e[ps[k]^1].c +=tr ;
maxf += tr , i = e[ps[top=f]].x ;
}
for(j = cur[i] ; j!=-1 ; j=cur[i]=e[j].next)
if(e[j].c > EPS && dep[e[j].y] == dep[i] + 1) break ;
if(j!=-1){
ps[top++] = j ; i = e[j].y ;
}else{
if(0==top) break ;
dep[i] = -1 , i = e[ps[--top]].x ;
}
}
}
return maxf ;
}
double calc(double mid){
int i ;
double sol ;
es = 0 ; memset(hd , -1 ,sizeof(hd)); S = n + 1 ; T = n + 2 ;
for(i = 1 ; i <= m ; ++i) {
ins(st[i] ,ed[i] , 1.0);
ins(ed[i] ,st[i] , 1.0);
}
for(i = 1 ; i <= n ;++i){
ins(S , i , m);
ins(i , T , m + 2*mid - dgr[i]);
}
return (m*n-MaxFlow())/2.0 ;
}
int vis[maxn] ;
void dfs(int x){
int i , y ;
vis[x] = 1 ;
for(i = hd[x] ; i!=-1 ; i=e[i].next)
if(e[i].c > EPS && !vis[y=e[i].y] )
dfs(y);
}
void work(){
int i , cnt ;
double sol , l = 0 , r = m , mid ;
while(sgn(l-r)){
mid = (l + r)/2.0 ;
sol = calc(mid);
if(sgn(sol) == 1){
l = mid ;
}else{
r = mid ;
}
}
//cout<<"Answer : " << l << endl ;
calc(l);
memset(vis , 0 ,sizeof(vis)); dfs(S) ;
cnt = 0 ;
for(i = 1 ; i <= n; ++i)
if(vis[i])
++ cnt ;
printf("%d\n" , cnt);
for(i = 1 ; i <= n ;++i)
if(vis[i])
printf("%d\n" , i);
}
int main(){
int i ;
while(scanf("%d%d" ,&n ,&m)!=EOF){
memset(dgr , 0 , sizeof(dgr));
for(i = 1 ; i<= m ;++i) {
scanf("%d%d" ,&st[i] ,&ed[i]);
dgr[st[i]] ++ ; dgr[ed[i]] ++ ;
}
if(m == 0){
printf("1\n1\n");
}else{
work();
}
}
return 0 ;
}
Problem E ： Destroying The Graph
提交网址：http://poj.org/problem?id=2125
参考程序：
#include<iostream>
using namespace std ;
const int maxV = 210 ;
const int maxE = maxV*maxV ;
const int INF = 2000000000 ;
struct node{
int x , y , c , next ;
};
node e[maxE] ;
int es , hd[maxV] ;
int Matrix[maxV][maxV] , Vcnt , Ecnt , S , T , N;
int in[maxV] , out[maxV];
void ins(int x ,int y ,int c){
e[es].x = x , e[es].y = y ,e[es].c = c , e[es].next = hd[x] , hd[x] = es ++ ;
e[es].x = y , e[es].y = x ,e[es].c = 0 , e[es].next = hd[y] , hd[y] = es ++ ;
}
int MaxFlow(){
int dep[maxV] , ps[maxV] , cur[maxV] ;
int tr , f , r , i , j , k , x , y ,top , maxf = 0 ;
while(1){
memset(dep , -1 ,sizeof(dep));
dep[S] = 0 ; f = r = 0 ; ps[r++] = S ;
while(f!=r){
x = ps[f++] ;
for(i = hd[x] ; i!=-1 ; i=e[i].next)
if(e[i].c && dep[y = e[i].y] == -1){
dep[y] = dep[x] + 1 ; ps[r++] = y ;
}
if(dep[T]!=-1) break ;
}
if(dep[T]==-1) break ;
i = S , top = 0 ; memcpy(cur ,hd , sizeof(hd));
while(1){
if(i == T){
for(tr = INF , k = 0 ; k < top ; ++ k)
if(e[ps[k]].c < tr ) tr = e[ps[f=k]].c ;
for(k = 0 ; k < top ; ++k)
e[ps[k]].c -= tr , e[ps[k]^1].c += tr ;
maxf += tr , i = e[ps[top = f]].x ;
}
for(j = cur[i] ; j!=-1 ; j = cur[i] = e[j].next)
if(e[j].c && dep[e[j].y] == dep[i] + 1) break ;
if(j !=-1){
ps[top++] = j ; i = e[j].y ;
}else{
if(top == 0) break ;
dep[i] = -1 ; i = e[ps[--top]].x ;
}
}
}
return maxf ;
}
int vis[maxV] ;
void dfs(int x){
int i , y ;
vis[x] = 1 ;
for(i = hd[x] ; i!=-1 ; i=e[i].next){
y = e[i].y ;
if(!vis[y] && e[i].c ){
dfs(y);
}
}
}
void work(){
int cnt , i ;
memset(vis , 0 , sizeof(vis));
printf("%d\n" , MaxFlow());
dfs(S);
cnt = 0 ;
for(i = 1; i <=Vcnt ; ++i){
if(!vis[i]) ++ cnt ;
if(vis[Vcnt+i]) ++ cnt;
}
printf("%d\n" , cnt);
for(i = 1 ; i <= Vcnt ; ++ i){
if(vis[Vcnt+i]) printf("%d +\n" , i);
if(!vis[i]) printf("%d -\n" , i);
}
}
int main(){
int i , j , x , y , w;
scanf("%d%d" , &Vcnt , &Ecnt);
es = 0 ;
memset(hd , -1 ,sizeof(hd));
N = 2*Vcnt + 2 ;
S = 2*Vcnt + 1 ;
T = 2*Vcnt + 2 ;
for(i = 1 ; i <= Vcnt ; ++ i) {
scanf("%d" , &w);
ins(i + Vcnt , T , w);
}
for(i = 1 ; i <= Vcnt ; ++ i){
scanf("%d" , &w);
ins(S , i , w);
}
for(i = 0 ; i < Ecnt ; ++ i){
scanf("%d%d" , &x , &y);
ins(x , y + Vcnt, INF);
}
work();
//while(getchar());
return 0;
}