其实早有Beyond The Void 大牛做了解题报告，非常犀利，Orz !
网址：http://www.byvoid.com/blog/lpf24-solution/
我从头做了一遍， 感觉受益匪浅。贴出自己代码，仅供参考。思路可参考Beyond牛。
好不容易找到了两个可提交的网站：
南开大学<可惜只有几个题>
http://acm.nankai.edu.cn/problem_search.php?q=24
南京邮电大学< 可惜没有Sepcial Judge >
http://acm.njupt.edu.cn/acmhome/problemList.do?method=show&page=7
飞行员配对方案问题
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 105 ;
int c[maxn][maxn] , prev[maxn] , n , m , S , T ;
int main()
{
cin>>m>>n ;
int x , y , i , j ;
memset(c , 0 ,sizeof(c));
while( (cin>> x >> y ) && ( x>0 && y>0 )) c[x][y] = 1 ;
S = n + 1 , T = n + 2 ;
for( i = 1 ; i<=m ; ++i ) c[S][i] = 1 ;
for( i = m + 1 ; i<=n ; ++ i ) c[i][T] = 1 ;
int maxf = 0 , v , u , w , del;
while(1)
{
queue<int> Q ; Q.push(S) ; memset(prev , -1 ,sizeof(prev));
while( ! Q.empty() )
{
v = Q.front() ; Q.pop() ;
for( u = 1 ; u <= T ; ++ u )
if( c[v][u] && prev[u] == -1 )
prev[u] = v , Q.push(u);
if( prev[T] !=-1 ) break ;
}
if( prev[T] ==-1 ) break ;
del = 200000000 ;
for( u = T , v = prev[T] ; u != S ; u = v , v = prev[v] )
del = min( del , c[v][u] ) ;
for( u = T , v = prev[T] ; u != S ; u = v , v = prev[v] )
c[v][u] -= del , c[u][v] += del ;
maxf += del ;
}
if( maxf == 0 )
cout<<"No Solution!"<<endl ;
else
{
cout<<maxf<<endl ;
for( i = 1 ; i<=m ; ++i )
{
for( j = m + 1 ; j<=n ; ++j )
if( c[j][i] == 1 )
{ cout<<i<<" "<<j<<endl ; break ; }
}
}
return 0 ;
}
太空飞行计划问题
#include<iostream>
#include<queue>
using namespace std ;
const int maxn = 110 ;
const int maxe = 2*maxn * maxn ;
const int inf = 1<<29 ;
struct node
{
int x, y , c , next ;
};
node e[maxe] ;
int n , m , S , T , N , es , hd[maxn] , used[maxn] ;
int cur[maxn] , ps[maxn] , dep[maxn] ;
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 dinic(){
int i ,j , v ,u ,k , top , tr , f ,r , maxf = 0;
while(1){
f = r = 0 ; memset(dep , -1 ,sizeof(dep));
ps[r++] = S ; dep[S] = 0 ;
while(f!=r){
v = ps[f++] ;
for(i = hd[v] ; i!=-1 ; i = e[i].next)
if(e[i].c && dep[e[i].y]==-1)
dep[e[i].y] = dep[v] + 1 , ps[r++] = e[i].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( 0 == top ) break ;
dep[i] = -1 ; i = e[ps[--top]].x ;
}
}
}
return maxf ;
}
int main(){
int i , j , k , Pi , v , sum = 0;
scanf("%d%d",&m,&n);
es = 0 ; memset(hd , -1 ,sizeof(hd));
S = m + n + 1 ; T = S + 1 ; N = T ;
for(i = 1 ; i<=m ; ++i){
scanf("%d",&Pi); sum += Pi ;
ins(n + i , T , Pi );
while(1){
if(getchar() == '\n') break;
scanf("%d",&v);
ins(v , n + i , inf);
}
}
for(i = 1 ; i<=n ; ++i){
scanf("%d",&Pi);
ins(S , i , Pi);
}
int ret = dinic() ;
memset(used , 0 ,sizeof(used));
queue<int> Q ;
Q.push(S); used[S] = 1 ;
while(!Q.empty()){
v = Q.front() ; Q.pop() ;
for(i = hd[v] ; i!=-1 ; i=e[i].next)
if(e[i].c && !used[e[i].y])
used[e[i].y] = 1 , Q.push(e[i].y);
}
for(i = n + 1 ; i<=n+m ; ++i)
if(!used[i]) printf("%d " , i - n);
printf("\n");
for(i = 1 ; i<=n ; ++i)
if(!used[i]) printf("%d " , i);
printf("\n");
printf("%d\n",sum - ret);
return 0 ;
}
最小路径覆盖问题
#include<iostream>
#include<string.h>
#include<math.h>
#define MAXN ( 155 )
using namespace std ;
int gh[MAXN][MAXN] , N , E ;
int xM[MAXN] , yM[MAXN] , chk[MAXN] ;
bool find(int u){
int v ;
for(v = 1 ; v <=N ; ++v)
if(gh[u][v]&&!chk[v]){
chk[v] = 1 ;
if(yM[v]==-1 || find(yM[v])){
yM[v] = u ; xM[u] = v ;
return true ;
}
}
return false;
}
int MaxMatch(){
int i , ret = 0 ;
memset(xM, -1 ,sizeof(xM));
memset(yM, -1 ,sizeof(yM));
for(i = 1 ; i<= N ; ++i )
if(xM[i]==-1){
memset(chk , 0 ,sizeof(chk));
if(find(i)) ++ret ;
}
return ret ;
}
int main(){
int i ,j , x , y , used[MAXN];
scanf("%d%d",&N,&E);
memset(gh , 0 , sizeof(gh));
for(i = 0 ; i<E ; ++i){
scanf("%d%d",&x,&y);
gh[x][y] = 1 ;
}
int ret = MaxMatch();
memset(used , 0 , sizeof(used));
for(i = 1 ; i<=N ; ++i)
if(!used[i]){
printf("%d",i) , used[i] = 1 ;
for(j = xM[i] ; j!=-1 ; j = xM[j])
if(!used[j]){
printf(" %d",j) ; used[j] = 1 ;
}
printf("\n");
}
printf("%d\n",N - ret);
return 0 ;
}
魔术球问题
#include<iostream>
#include<math.h>
using namespace std ;
const int maxn = 2*2005 ;
const int maxe = 70*70*70*2 ;
const int inf = 1<<29 ;
struct node{
int x , y , c , next ;
};
node e[maxe] ;
int hd[maxn] , es , S ,T , N ;
int cur[maxn] , ps[maxn] , dep[maxn] , next[maxn] , used[maxn];
bool reach(int x ,int y){
int tp = (int)sqrt((double)(x+y));
return tp*tp == x+y ;
}
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 dinic(){
int f , r , top , i , j , k , tr , maxf = 0 , v , u ;
while(1){
f = r = 0 ; memset(dep , -1 , sizeof(dep));
ps[r++] = S , dep[S] = 0 ;
while(f!=r){
v = ps[f++] ;
for(i = hd[v] ; i!=-1 ; i = e[i].next)
if(e[i].c && dep[ e[i].y ]==-1)
ps[r++] = e[i].y , dep[e[i].y] = dep[v] + 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(k = 0 , tr = inf ; 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[cur[i]].next)
if(e[j].c && dep[e[j].y] == dep[i] + 1) break;
if(cur[i]!=-1){
ps[top++] = j ; i = e[j].y ;
}
else {
if(0 == top ) break;
dep[i] = -1 ; i = e[ps[--top]].x ;
}
}
}
return maxf ;
}
int main(){
int n , vcnt , i , j ,k , v ;
scanf("%d",&n);
printf("%d\n",vcnt=(n*n+2*n-1)/2);
S = 2*vcnt + 1 ; T = S + 1 ; N = T ;
es = 0 ; memset(hd , -1 ,sizeof(hd));
for(i = 1 ; i<=vcnt ;++i)
for(j = 1 ; j<i ; ++j)
if(reach(i,j))
ins(i , vcnt + j , 1) ;
for(i = 1 ; i<=vcnt ; ++i){
ins(S , i , 1); ins(vcnt + i , T , 1);
}
int ret = dinic();
memset(next , -1 ,sizeof(next)); memset(used , 0 , sizeof(used));
for(i = 1 ; i<=vcnt ; ++i)
for(j = hd[i] ; j!=-1 ; j=e[j].next)
if((k = e[j].y) > vcnt && k <=2*vcnt && !e[j].c ){
k -= vcnt ;
next[k] = i ;
}
for(i = 1 ; i<=vcnt ; ++i)
if(!used[i]){
if(next[i]==-1)
printf("%d \n",i) , used[i] = 1 ;
else{
printf("%d",i); used[i] = 1 ;
for(j = next[i] ; j!=-1 ; j = next[j])
printf(" %d",j), used[j] = 1 ;
printf(" \n");
}
}
return 0 ;
}
圆桌问题
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<queue>
using namespace std ;
const int maxn = 150 + 275 ;
const int maxe = maxn * maxn ;
const int inf = 1<<28 ;
struct node
{
int x, y , c , next ;
} ;
node bf[maxe] ;
int hd[maxn] , cur[maxn] , ps[maxn] , dep[maxn] , ne , N ,S ,T ;
void ins(int x ,int y , int c )
{
bf[ne].x = x , bf[ne].y = y ,bf[ne].c = c , bf[ne].next = hd[x] , hd[x] = ne ++ ;
bf[ne].y = y , bf[ne].y = x , bf[ne].c = 0, bf[ne].next =hd[y] , hd[y] = ne ++ ;
}
int maxflow()
{
int tr , res = 0 ;
int i , j , k , f , r, top ;
while(1){
memset(dep , -1 ,sizeof(dep)) ;
for( f = dep[S] = 0 , ps[0] = S , r = 1 ; f!=r ; )
for( i = ps[f++] , j = hd[i] ; j !=-1 ; j = bf[j].next )
if( bf[j].c && -1 == dep[ k = bf[j].y ] )
{
dep[k] = dep[i] + 1 , ps[r++] = k ;
if( k == T ) { f = r ; break ; }
}
if( -1 == dep[T] ) break ;
memcpy(cur , hd , N * sizeof(int) ) ;
for( i = S , top = 0 ; ; ){
if( i == T ) {
for( k = 0 , tr = inf ; k<top ; ++k )
if( bf[ ps[k] ].c < tr )
tr = bf[ ps[f = k] ].c ;
for( k = 0 ; k<top ; ++k )
bf[ps[k]].c -= tr , bf[ps[k]^1].c += tr ;
res += tr ; i = bf[ ps[top = f] ].x ;
}
for( j = cur[i] ; cur[i]!=-1 ; j = cur[i] = bf[cur[i]].next )
if( bf[j].c && dep[i] + 1 == dep[ bf[j].y ] ) break ;
if( cur[i]!=-1 ) {
ps[top ++ ] = cur[i] ; i = bf[ cur[i] ].y ;
}
else {
if( top == 0 ) break ;
dep[i] = -3 , i = bf[ ps[--top] ].x ;
}
}
}
return res ;
}
int main()
{
int n , m , r , c , i , j , sup = 0, dmd = 0 ;
cin>>n>>m ;
N = n + m + 2 ;
S = n + m + 1 ;
T = n + m + 2 ;
memset(hd , -1 , sizeof(hd)) ;
ne = 0 ;
for( i = 1 ; i<=n; ++i )
{
cin>>r ; ins(S , i , r ) ; sup += r ;
}
for( i = 1 ; i<=m ;++i )
{
cin>>c ; ins(n + i , T , c) ; dmd += c ;
}
for( i = 1 ; i<=n ; ++i )
for( j = m; j>=1; --j )
ins(i , n + j , 1);
int ret = maxflow() ;
if( ret == sup )
cout<<"1"<<endl ;
else
cout<<"0"<<endl ;
for( i = 1 ; i<=n ; ++ i )
{
for( j = hd[i] ; j!=-1 ; j = bf[j].next )
if( bf[j].c == 0 )
cout<<bf[j].y - n <<" ";
cout<<endl ;
}
return 0 ;
}最长递增子序列问题
#include<iostream>
using namespace std ;
const int SIZE = 501;
const int maxn = 2*SIZE + 5 ;
const int maxe = maxn * maxn ;
const int inf = 1<<29 ;
int opt[SIZE] , a[SIZE] , n , ans ;
struct node{
int x ,y , c , next;
};
node e[maxe] ;
int es, hd[maxn] , S , T , N ;
int cur[maxn] , ps[maxn] , dep[maxn] ;
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 dinic()
{
int i ,j , u ,v , k , tr , f, r , maxf = 0 , top ;
while(1)
{
f = r = 0 ; memset(dep , -1 ,sizeof(dep));
ps[r++] = S , dep[S] = 0 ;
while(f!=r)
{
v = ps[f++] ;
for(i = hd[v] ; i !=-1 ; i=e[i].next)
{
u = e[i].y ;
if(e[i].c && dep[u] == -1)
dep[u] = dep[v] + 1 , ps[r++] = u ;
}
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(k = 0 , tr = inf ; k < top ; ++ k)
if(e[ps[k]].c < tr ) tr = e[ps[k]].c , f = k ;
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[i]+1 == dep[ e[j].y ]) 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 ;
}
inline int P(int i , int t){ return 2*(i-1)+ t + 1 ;}
void ans_1(){
int i ,j ;
opt[1] = 1 ;
for(i=2; i<=n ; ++i){
opt[i] = 1 ;
for(j = 1 ; j<i ; ++j)
if(a[i] >= a[j])
opt[i] = max(opt[i] , opt[j] + 1) ;
}
ans = 0 ;
for(i = 1 ; i<=n ; ++i)
ans = max(ans , opt[i]);
printf("%d\n",ans);
}
void ans_2(){
int i , j ;
es = 0 ; memset(hd , -1 , sizeof(hd));
S = 2*n + 1 , T = 2*n+2 , N = T ;
for(i = 1; i<=n ; ++i){
ins(P(i , 0) , P(i , 1) , 1);
if(opt[i] == ans)
ins(S , P(i,0) , 1);
if(opt[i] == 1)
ins( P(i,1) , T , 1 );
}
for(i = 2; i<=n ; ++i)
for(j = 1 ; j<i ; ++j)
if(a[i]>=a[j] && opt[i] == opt[j] + 1)
ins( P(i , 1) , P(j , 0 ) , 1);
int ret = dinic();
printf("%d\n",ret);
}
void ans_3(){
int i , j ;
if(ans == 1) { printf("%d\n",n) ; return ; }
es = 0 ; memset(hd , -1 ,sizeof(hd));
S = 2*n + 1 , T = 2*n + 2 ; N = T ;
ins(P(1,0) , P(1,1) , inf) ; ins(P(n,0) , P(n,1) , inf) ; ins(P(1,1), T,inf);
if(opt[n] == ans)
ins(S , P(n,0) , inf ) ;
for(i = 2 ; i <=n ; ++i){
ins(P(i,0),P(i,1),1);
if(opt[i] == ans)
ins(S,P(i,0),1);
if(opt[i] == 1)
ins(P(i,1),T ,1);
}
for(i = 2; i<=n ; ++i)
for(j = 1 ; j<i ; ++j)
if(a[i]>=a[j] && opt[i] == opt[j] + 1)
ins( P(i , 1) , P(j , 0 ) , 1);
int ret = dinic();
printf("%d\n",ret);
}
int main(){
int i;
scanf("%d",&n);
for(i = 1 ; i<=n ; ++i)
scanf("%d",&a[i]);
ans_1();
ans_2();
ans_3();
return 0 ;
}
试题库问题
#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std ;
const int MAXN = 1030;
const int maxint = 200000000 ;
int c[ MAXN ][ MAXN ] ;
int pbm , kind , S , T , N , need;
int prev[ MAXN ] ;
bool maxflow()
{
int maxf = 0 , v , u , w ,del ;
while(1)
{
queue<int> Q ; Q.push(S);
memset(prev , -1 , sizeof(prev));
while(! Q.empty() )
{
v = Q.front() ; Q.pop() ;
for( u = 1 ; u <= N ; ++ u )
if( c[v][u] && prev[u] == -1 )
prev[u] = v , Q.push(u);
if( prev[T] > 0 ) break ;
}
if( prev[T] < 0 ) break ;
del = maxint ;
for( v = T , u = prev[v] ; v != S ; v = u , u = prev[u] )
if( del > c[u][v] ) del = c[u][v];
for( v = T , u = prev[v] ; v != S ; v = u , u = prev[u] )
c[u][v] -= del , c[v][u] += del ;
maxf += del ;
}
return maxf == need ;
}
void solve()
{
if( ! maxflow() )
{
cout<<"No Solution!"<<endl ;
return ;
}
int i , j ;
for( i = pbm + 1 ; i <= pbm + kind ; ++ i )
{
cout<<i - pbm <<":" ;
for( j = 1 ; j<=pbm ; ++ j )
if( c[i][j] == 1 )
cout<<" "<<j ;
cout<<endl ;
}
}
void read()
{
cin>>kind>>pbm ;
memset(c , 0 ,sizeof(c));
S = pbm + kind + 1 ;
N = T = pbm + kind + 2 ;
need = 0 ;
int i , j , cnt , v ;
for( i = 1 ; i <= kind ; ++ i )
{
cin>>c[ pbm + i ][T] ; need += c[pbm + i][T] ;
}
for( i = 1 ; i <= pbm ; ++i )
{
c[ S ][ i ] = 1 ;
cin>> cnt ;
for( j = 1 ; j<=cnt ; ++j )
{
cin>>v ;
c[i][ pbm + v] = 1;
}
}
}
int main()
{
read();
solve();
return 0 ;
}
机器人路径规划问题
方格取数问题
#include<iostream>
using namespace std ;
const int grid = 30;
const int maxn = grid * grid ;
const int maxe = maxn * 10 ;
const int inf = 200000000 ;
int mat[grid][grid] ;
int dx[4]={1,0 ,-1,0} , dy[4]={0,1,0,-1};
struct node
{
int x , y , c , next ;
} ;
struct network
{
int S , T , N , es , hd[maxn] ;
node e[maxe] ;
int ps[maxn] , cur[maxn] , dep[maxn] ;
void init(int vS , int vT ,int vN) ;
void ins(int x,int y ,int c) ;
int dinic() ;
} ;
void network::init(int vS ,int vT ,int vN)
{
S = vS , T = vT , N = vN ;
es = 0 ; memset(hd , -1 ,sizeof(hd));
}
void network::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 network::dinic()
{
int u , v , f , r , i ,j, k , tr , top , maxf = 0 ;
while(1)
{
f = r = 0 ; memset(dep , -1 ,sizeof(dep));
ps[r++] = S , dep[S] = 0 ;
while(f != r )
{
v = ps[f++] ;
for(i = hd[v] ; i !=-1 ; i = e[i].next){
u = e[i].y ;
if(e[i].c && dep[u]==-1 )
dep[u] = dep[v] + 1 , ps[r++] = u ;
}
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(k = 0 , tr = inf ; k < top ; ++ k)
if( tr > e[ps[k]].c ) tr = e[ps[k]].c , f = k ;
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 ; // The only end for while(1);
dep[i]=-1 , i = e[ps[--top]].x ;
}
}
}
return maxf ;
}
bool out(int x ,int y , int n ,int m)
{
return x < 0 || y < 0 || x >= n || y >=m ;
}
int main()
{
int n , m , S , T , N , x , tot = 0 ,i , j , k ;
cin>>n>>m ;
network gh ;
S = n * m + 1 ; T = S + 1 ; N = T ;
gh.init(S , T , N) ;
for(i = 0 ; i<n ; ++ i)
for(j = 0 ; j<m ;++j)
{
cin>>mat[i][j] ;
tot += mat[i][j] ;
}
for(i = 0 ; i < n ; ++ i )
for(j = 0 ; j < m ; ++ j )
if((i + j) % 2 == 0 )
gh.ins(S , i*m+j+1 , mat[i][j]) ;
else
gh.ins(i*m+j+1 , T , mat[i][j]) ;
for(i = 0 ; i<n ; ++i)
for(j = 0 ; j<m ; ++j)
if((i+j)%2 == 0 ) // set X
for(k = 0 ; k < 4 ; ++k)
{
int cx = i + dx[k] , cy = j + dy[k] ;
if(out(cx, cy , n , m) ||(cx + cy)%2 == 0 ) continue ;
gh.ins(i * m + j + 1 , cx * m + cy + 1 , inf ) ;
}
cout<<tot-gh.dinic()<<endl ;
//while(getchar());
return 0 ;
}
餐巾计划问题
航空路线问题
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<vector>
#include<string.h>
using namespace std ;
const int maxn = 110 ;
const int maxe = maxn * maxn ;
const int inf = 1<<28 ;
struct node
{
int v , c , cost , next ;
} ;
struct network
{
int S ,T , N , hd[maxn] , es ;
int vis[maxn] , prev[maxn] , pos[maxn] , d[maxn] ;
node e[maxe] ;
void init(int vS , int vT , int vN ) ;
void ins(int u ,int v ,int c ,int cost) ;
bool spfa() ;
int mcmf() ;
} ;
void network::init(int vS ,int vT ,int vN)
{
S = vS , T =vT , N = vN ;
es = 0 , memset(hd , -1,sizeof(hd)) ;
}
void network::ins(int u ,int v,int c,int cost)
{
e[es].v = v , e[es].c = c, e[es].cost =cost ,e[es].next = hd[u] , hd[u] = es ++ ;
e[es].v = u , e[es].c = 0, e[es].cost =-cost,e[es].next = hd[v] , hd[v] = es ++ ;
}
bool network::spfa()
{
int u , v , i ; queue<int> Q ;
for( i = 1 ; i<=N ; ++i ) vis[i] = 0 , prev[i]=-1 ,d[i] = inf ;
vis[S] = 1 , Q.push(S) , d[S] = 0 ;
while(!Q.empty() )
{
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for( i = hd[v] ; i!=-1 ; i=e[i].next )
{
u = e[i].v ;
if( e[i].c && d[u] > d[v] + e[i].cost )
{
d[u] = d[v] + e[i].cost ; prev[u] = v ; pos[u]=i ;
if(!vis[u]) vis[u]=1 ,Q.push(u) ;
}
}
}
return prev[T]!=-1 ;
}
int network::mcmf()
{
int take = 0 , del , u ;
while(spfa())
{
del = inf ;
for( u = T ; u!=S ; u=prev[u] ) del = min( del , e[pos[u]].c ) ;
for( u = T ; u!=S ; u=prev[u] ) e[pos[u]].c -= del , e[pos[u]^1].c += del ;
take += del * d[T] ;
}
return take ;
}
struct city
{
char cy[41] ;
} ;
city vec[100] ;
int city_cnt , route_cnt ;
int find(char * s )
{
int i ;
for( i = 1 ; i<=city_cnt ; ++ i)
if( !strcmp(s , vec[i].cy) ) return i ;
}
void solve()
{
int i , j , vs , vt , S , T , N , ret , x, y;
char fst[41] , sec[41] ;
network gh ;
cin>>city_cnt>>route_cnt ;
N = 2*city_cnt , S = 1 , T = 2*city_cnt ;
gh.init(S , T , N ) ;
gh.ins(1 , 2 , 2 , -1 ) ; gh.ins(T - 1 , T , 2 , -1 ) ;
for( i = 2 ; i<city_cnt ; ++ i )
gh.ins(2*i - 1 , 2*i , 1 , -1 ) ;
for( i = 1 ; i <= city_cnt ; ++ i )
cin>>vec[i].cy ;
for( i = 1 ; i<=route_cnt ; ++ i )
{
cin>>fst>>sec ;
vs = find(fst) ; vt = find(sec) ;
if( vs > vt ) swap(vs , vt) ;
gh.ins(2*vs , 2*vt - 1 , 1 , 0 ) ;
}
ret = gh.mcmf() + 2 ;
cout<<-ret<<endl ;
}
int main()
{
solve() ;
return 0 ;
}
软件补丁问题
本题书上描述有误：
原文：
补丁pi将修复某些错误而同时加入某些错误，设错误集合Fi-、Fi+，使用过补丁pi之后，Fi-中的任何错误都不会在软件中出现，而软件将包含Fi+中的所有错误， 同样Fi-、Fi+交集为空。另外，使用每个补丁都要耗一定的时间（即补丁程序的运行时间）。
错误原因：
王晓东书中将F1[]与F2[]正好搞反了。 害的我查了半天错误。
#include<iostream>
#include<queue>
#define shl(x,i) ((x)<<(i))
#define shr(x,i) ((x)>>(i))
#define bit(x,i) ((x)&shl(1,i) ? 1:0)
#define rev(x,i) ((x)^(shl(1,i)-1) )
using namespace std ;
const int maxn = (1<<20) + 5 ;
const int ms = 101 ;
const int inf = 1<<29 ;
int d[maxn] , t[ms] , b1[ms] , b2[ms] , f1[ms] , f2[ms];
bool vis[maxn] ;
int scnt , n ;
inline int getp(int a ,int i ){
if( ((a&b1[i]) == b1[i]) && ((a&b2[i]) == 0) )
return (a|f1[i])&rev(f2[i],n) ;
else
return -1 ;
}
int work(){
int i , j ,v , u , S , T;
queue<int> Q ;
for(i = 0 ; i<(1<<n) ; ++i)
d[i] = inf , vis[i] = 0 ;
S = (1<<n)-1 ; T = 0 ;
d[S] = 0 , vis[S] = 1 , Q.push(S);
while(!Q.empty()){
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for(i = 0 ; i<scnt ; ++i)
if((u = getp(v , i))!=-1 && d[u] > d[v] + t[i] ){
d[u] = d[v] + t[i] ;
if(vis[u] == 0){
vis[u] = 1 ; Q.push(u);
}
}
}
return d[T] == inf ? 0 : d[T] ;
}
int main(){
int i , j , ret ;
char B[25],F[25] ;
scanf("%d%d",&n,&scnt);
for(i = 0 ; i<scnt ;++i){
b1[i]=b2[i]=f1[i]=f2[i]=0 ;
scanf("%d%s%s",&t[i],B,F);
for(j = 0 ; j<n ; ++j){
if(B[j]=='+') b1[i] += 1<<j ; // need
if(B[j]=='-') b2[i] += 1<<j ; // not need
if(F[j]=='+') f1[i] += 1<<j ; // repair
if(F[j]=='-') f2[i] += 1<<j ; // produce
}
}
ret = work();
printf("%d\n",ret);
return 0 ;
}
星际转移问题
#include<iostream>
#include<queue>
using namespace std ;
const int inf = 1<<29 ;
const int MaxT = 1000 ;
const int MaxN = 25 ;
const int MaxM = 20 ;
const int MaxK = 55 ;
const int maxn = (MaxN + 2)*( MaxT + 2 ) ;
const int maxe = 3*(MaxT + 1)*(MaxN + MaxM + 2) ;
struct node{
int x, y , c, next ;
};
node e[maxe] ;
int es , hd[maxn] , S , T , N , maxf ;
int n , m , K ;
int pos[MaxN][MaxN] , circle[MaxN] , H[MaxN] ;
int used[MaxN] , chk[MaxN][MaxN];
int cur[maxn] , ps[maxn] , dep[maxn] ;
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 dinic(){
int i ,j , v ,u ,k , top , tr , f ,r ;;
while(1){
f = r = 0 ; memset(dep , -1 ,sizeof(dep));
ps[r++] = S ; dep[S] = 0 ;
while(f!=r){
v = ps[f++] ;
for(i = hd[v] ; i!=-1 ; i = e[i].next)
if(e[i].c && dep[e[i].y]==-1)
dep[e[i].y] = dep[v] + 1 , ps[r++] = e[i].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( 0 == top ) break ;
dep[i] = -1 ; i = e[ps[--top]].x ;
}
}
}
return maxf ;
}
inline int P(int ti ,int vi){
return ti * (n + 2) + vi + 1;
}
int no_answer(){
int i , j , v ;
memset(chk , 0 ,sizeof(chk));
memset(used, 0 ,sizeof(used));
for(i = 0 ; i < m ; ++i)
for(j = 0 ; j < circle[i] ; ++j)
chk[pos[i][j]][pos[i][j+1]] = 1 ;
queue<int> Q ; Q.push(0) ; used[0] = 1 ;
while(!Q.empty()){
v = Q.front() ; Q.pop() ;
for( i = 0 ; i < n + 2 ; ++i)
if(chk[v][i]&&!used[i])
used[i] = 1 , Q.push(i) ;
if(used[n+1] == 1) break ;
}
return used[n+1]==0 ;
}
int work(){
int v , u , i , j , t ;
es = 0 ; memset(hd , -1 ,sizeof(hd));
scanf("%d%d%d",&n,&m,&K); // n station , m boat , K people
for(i = 0 ; i < m ; ++i){
scanf("%d%d",&H[i],&circle[i]);
for(j = 0 ; j < circle[i] ; ++j){
scanf("%d",&pos[i][j]);
if( pos[i][j] == -1 ) pos[i][j] = n + 1 ;
}
pos[i][j] = pos[i][0] ;
}
if(no_answer()) return 0 ;
S = maxn - 3; T = S + 1 ;
ins(S , P(0,0) , inf) ; ins(P(0,n+1),T ,inf) ;
for(t = 1 , maxf = 0 ; maxf < K ; ++t){
ins(S , P(t,0) , inf ) ; ins(P(t,n+1),T ,inf) ;
for(i = 0 ; i < n + 2 ; ++ i)
ins( P(t-1,i) , P(t,i) , inf) ;
for(i = 0 ; i < m ; ++ i){
v = pos[i][(t-1)%circle[i]] ; u = pos[i][t%circle[i]] ;
ins( P(t-1,v), P(t,u) , H[i]) ;
}
dinic() ;
}
return t - 1 ;
}
int main(){
printf("%d\n",work()) ;
return 0 ;
}
孤岛营救问题
#include<iostream>
#include<stdlib.h>
#include<queue>
#include<memory.h>
#define WALL 0
#define YES (-1)
using namespace std ;
const int maxkey = 11 ;
const int grid = 11 ;
struct node
{
int x , y , key ;
node() {}
node(int vX ,int vY ,int vKey):
x(vX) , y(vY) , key(vKey) {}
} ;
int dx[]={1,0,-1,0} , dy[]={0,1,0,-1} ;
int used[ grid * grid ][ (1<<maxkey) ] ;
int bd[grid][grid] ;
int nbr[grid * grid][4] ;
int n , m , K , keycnt , P ;
inline int hash(int x ,int y)
{
return x * m + y ;
}
inline int out(int x ,int y)
{
return x<0 || y<0 || x>=n || y>=m ;
}
inline int fdir(int x1 ,int y1 , int x2 ,int y2)
{
for(int i = 0 ; i<4 ; ++i)
if( (x1 + dx[i] == x2 ) && (y1 + dy[i] == y2) ) return i ;
}
inline bool End(node cur)
{
return cur.x == n-1 && cur.y == m-1 ;
}
int can()
{
memset(used , -1 ,sizeof(used));
int i , j , t ;
queue<node> Q ;
node cur(0 , 0 , 0 ) , son ;
if(bd[0][0] !=0 ) cur.key |= (1<<bd[0][0]) ;
used[hash(cur.x,cur.y)][cur.key] = 0 ; Q.push(cur) ;
while(! Q.empty())
{
cur = Q.front() ; Q.pop() ;
for(i = 0 ; i<4 ; ++i)
{
son=node(cur.x + dx[i] , cur.y+dy[i] , cur.key );
t = nbr[ hash(cur.x , cur.y) ][ i ] ;
if( out(son.x,son.y) || t == WALL || ( t > 0 && !( cur.key & (1<<t )) ) )
continue ;
if(bd[son.x][son.y])
son.key |= bd[son.x][son.y] ;
if( used[hash(son.x,son.y)][son.key] != -1) continue ;
t = used[hash(son.x,son.y)][son.key] = used[hash(cur.x,cur.y)][cur.key] + 1 ;
if( End(son) ) return t ;
Q.push(son);
}
}
return -1 ;
}
int main()
{
int i , x1 , y1 , x2 , y2 , gi ,j, keycnt , keyid;
memset(bd , 0 , sizeof(bd));
memset(nbr, YES , sizeof(nbr));
cin>>n>>m>>P ;
cin>>K ;
for(i = 0 ; i<K ; ++i)
{
cin>>x1>>y1>>x2>>y2>>gi ;
-- x1 , -- y1 , -- x2, -- y2 ;
j = fdir(x1, y1,x2,y2); nbr[ x1*m + y1 ][j] = gi ;
j = fdir(x2, y2,x1,y1); nbr[ x2*m + y2 ][j] = gi ;
}
cin>>keycnt ;
for(i = 0 ; i<keycnt ; ++i)
{
cin>>x1>>y1>>keyid ;
-- x1 , -- y1 ;
bd[x1][y1] |= (1<<keyid) ;
}
int take = can() ;
cout<< take <<endl ;
return 0 ;
}
汽车加油行驶问题
#include<iostream>
#include<queue>
using namespace std ;
const int grid = 105 ;
const int maxn = grid * grid * 11 ;
const int maxe = 4 * maxn ;
const int inf = 1<<30 ;
struct node
{
int y , c, next;
} ;
int hd[maxn] , S ,T , Vcnt, es ;
node e[maxe] ;
int N , K , A , B ,C , bd[grid][grid];
int dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1} , oil[4] ;
int hash(int x , int y ,int t )
{
return t*N*N + x*N + y + 1 ;
}
void ins(int x , int y , int w)
{
e[es].y = y , e[es].c = w,
e[es].next = hd[x] , hd[x] = es ++ ;
}
bool out(int x,int y)
{ return x < 0 || y < 0 || x>=N || y>=N ; }
void readln()
{
int i , j , t , u , x , y , cost;
cin>>N>>K>>A>>B>>C ;
for(i = 0 ; i < N ; ++i)
for( j = 0 ; j < N ; ++j)
cin>>bd[i][j] ;
S = hash(0,0,K) , T = hash(N-1,N-1,K) + 1 , Vcnt = T ;
es = 0 ; memset(hd , -1 , sizeof(hd)) ;
oil[0]=0 , oil[1] = 0 , oil[2] = B , oil[3] = B ;
for(i = 0 ;i < N ; ++i)
for(j = 0 ; j < N ; ++j)
for(t = 0 ; t <= K ; ++ t)
{
if( bd[i][j] && t < K)
{ ins( hash(i , j ,t ) , hash(i ,j , K ) , A ) ; continue ; }
if( t == 0 )
{ ins( hash(i, j , 0 ) , hash(i ,j , K) , C + A) ; continue ; }
for(u = 0 ; u < 4 ; ++ u)
{
x = i + dx[u] , y = j + dy[u] ;
if( out(x ,y ) ) continue ;
ins( hash(i , j , t ) , hash(x ,y , t -1 ) , oil[u] ) ;
}
}
for(i = 0 ; i <= K ; ++i)
ins( hash(N-1,N-1,i) , T , 0 );
}
int dist[maxn] , vis[maxn];
int SPFA()
{
int i , j ,v , u;
queue<int> Q ;
for(i = 1 ; i <= Vcnt ; ++i) dist[i] = inf , vis[i] = 0 ;
Q.push(S) ; dist[S] = 0 ; vis[S] = 1 ;
while(!Q.empty())
{
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for(i = hd[v] ; i!=-1 ; i = e[i].next)
{
u = e[i].y ;
if(dist[u] > dist[v] + e[i].c )
{
dist[u] = dist[v] + e[i].c ;
if(vis[u]==0) vis[u] = 1 , Q.push(u) ;
}
}
}
return dist[T] ;
}
int main()
{
readln();
int ret = SPFA();
cout<<ret<<endl;
return 0 ;
}
数字梯形问题
#include<iostream>
#include<queue>
using namespace std ;
const int grid = 21 ;
const int maxn = 2 * (grid +grid)* grid + 5 ;
const int maxe = 8 * maxn ;
const int inf = 1<<28;
struct node
{
int y , c , cost , next ;
} ;
int S ,T , N , hd[maxn] , es ;
node e[maxe] ;
int vis[maxn] , d[maxn] , pos[maxn] , prev[maxn] ;
int n , m , data[grid][grid] , cnt[grid][grid] ;
inline int P(int x,int y ,int t) { return 2*cnt[x][y] + t ; }
void readln()
{
int i , j , CH = 1 ;
cin>>m>>n ;
for(i = 1 ; i<= n ; ++i )
for(j = 1 ; j <= m+i-1 ; ++j)
cin>>data[i][j] , cnt[i][j] = CH++ ;
}
void init()
{
S = maxn - 2 , T = maxn - 1 , N = T ;
es = 0 ; memset(hd, -1 ,sizeof(hd));
}
void ins(int x,int y ,int c,int cost )
{
e[es].y = y, e[es].c = c, e[es].cost = cost, e[es].next = hd[x] , hd[x] = es ++ ;
e[es].y = x, e[es].c = 0, e[es].cost = -cost,e[es].next = hd[y] , hd[y] = es ++ ;
}
bool SPFA()
{
int i , v ,u ;
queue<int> Q ;
for(i = 1; i <=N ; ++i) d[i] = inf , vis[i] = 0 , prev[i] = -1 ;
Q.push( S ); d[S] = 0 ; vis[S] = 1 ;
while(!Q.empty())
{
v = Q.front() ; Q.pop() ; vis[v]=0 ;
for(i = hd[v] ; i!=-1 ; i = e[i].next)
{
u = e[i].y ;
if( e[i].c && d[u] > d[v] + e[i].cost)
{
d[u] = d[v] + e[i].cost ; prev[u] = v ; pos[u] = i ;
if( vis[u] == 0)
vis[u] = 1 , Q.push(u);
}
}
}
return prev[T]!=-1;
}
int MCMF()
{
int res = 0 , del , u ;
while(SPFA())
{
del = inf ;
for(u = T ; u!=S ; u = prev[u] )
if(del > e[pos[u]].c ) del = e[pos[u]].c;
for(u = T ; u!=S ; u= prev[u])
e[pos[u]].c -= del , e[pos[u]^1].c += del ;
res += del * d[T] ;
}
return res ;
}
void ans_1()
{
int i , j;
init();
for(i = 1 ; i<=m ; ++i)
ins( S , P(1 ,i ,0) , 1 , 0 );
for(i = 1 ; i<=n+m-1 ; ++i)
{
ins( P(n , i , 1 ) , T , 1 , 0 );
ins( P(n , i , 0 ) , P(n , i , 1 ) , 1 , -data[n][i]);
}
for(i = 1 ; i<=n-1 ; ++i)
for(j = 1 ; j<=m+i-1; ++j)
{
ins( P(i,j,0) , P(i,j,1) , 1 , -data[i][j]);
ins( P(i,j,1) , P(i+1,j,0) , 1 , 0 );
ins( P(i,j,1) , P(i+1,j+1,0) , 1 , 0 );
}
int ret = MCMF();
cout<< - ret<<endl;
}
void ans_2()
{
int i , j;
init();
for(i = 1 ; i<=m ; ++i)
ins(S , cnt[1][i] , 1 , -data[1][i]) ;
for(i = 1 ; i<=n+m-1 ;++i)
ins(cnt[n][i] , T , m , 0);
for(i = 1 ; i<=n-1; ++i )
for(j = 1 ; j<=m+i-1 ; ++j)
{
ins(cnt[i][j] , cnt[i+1][j] , 1 , - data[i+1][j] ) ;
ins(cnt[i][j] , cnt[i+1][j+1] , 1 , - data[i+1][j+1]);
}
int ret = MCMF();
cout<< - ret<<endl;
}
void ans_3()
{
int i , j ;
init();
for(i = 1 ; i<=m ; ++i)
ins( S , P(1 ,i ,0) , 1 , 0 );
for(i = 1 ; i<=n+m-1 ; ++i)
{
ins( P(n , i , 1 ) , T , m , 0 );
ins( P(n , i , 0 ) , P(n , i , 1 ) , m , -data[n][i]);
}
for(i = 1 ; i<=n-1 ; ++i)
for(j = 1 ; j<=m+i-1; ++j)
{
ins( P(i,j,0) , P(i,j,1) , m , -data[i][j]);
ins( P(i,j,1) , P(i+1,j,0) , m , 0 );
ins( P(i,j,1) , P(i+1,j+1,0) , m , 0 );
}
int ret = MCMF();
cout<<-ret<<endl;
}
int main()
{
readln();
ans_1();
ans_2();
ans_3();
return 0 ;
}
运输问题
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std ;
const int maxn = 210 ;
const int maxe = maxn * maxn ;
const int inf = 1<<28 ;
struct node
{
int v , c , cost , next ;
} ;
struct network
{
int S ,T , N , hd[maxn] , es ;
int vis[maxn] , prev[maxn] , pos[maxn] , d[maxn] ;
node e[maxe] ;
void init(int vS , int vT , int vN ) ;
void ins(int u ,int v ,int c ,int cost) ;
bool spfa() ;
int mcmf() ;
} ;
void network::init(int vS ,int vT ,int vN)
{
S = vS , T =vT , N = vN ;
es = 0 , memset(hd , -1,sizeof(hd)) ;
}
void network::ins(int u ,int v,int c,int cost)
{
e[es].v = v , e[es].c = c, e[es].cost =cost ,e[es].next = hd[u] , hd[u] = es ++ ;
e[es].v = u , e[es].c = 0, e[es].cost =-cost,e[es].next = hd[v] , hd[v] = es ++ ;
}
bool network::spfa()
{
int u , v , i ; queue<int> Q ;
for( i = 1 ; i<=N ; ++i ) vis[i] = 0 , prev[i]=-1 ,d[i] = inf ;
vis[S] = 1 , Q.push(S) , d[S] = 0 ;
while(!Q.empty() )
{
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for( i = hd[v] ; i!=-1 ; i=e[i].next )
{
u = e[i].v ;
if( e[i].c && d[u] > d[v] + e[i].cost )
{
d[u] = d[v] + e[i].cost ; prev[u] = v ; pos[u]=i ;
if(!vis[u]) vis[u]=1 ,Q.push(u) ;
}
}
}
return prev[T]!=-1 ;
}
int network::mcmf()
{
int take = 0 , del , u ;
while(spfa())
{
del = inf ;
for( u = T ; u!=S ; u=prev[u] ) del = min( del , e[pos[u]].c ) ;
for( u = T ; u!=S ; u=prev[u] ) e[pos[u]].c -= del , e[pos[u]^1].c += del ;
take += del * d[T] ;
}
return take ;
}
int main()
{
network gh ;
int n , m , S, T , N , i , j , sup[maxn] , dmd[maxn] , cost[maxn][maxn] ;
cin>>m>>n ; S = n + m + 1 , T = S + 1 , N = T ;
gh.init(S , T , N) ;
for( i = 1 ; i<=m ; ++i )
{
cin>>sup[i] ; gh.ins(S , i , sup[i] , 0) ;
}
for( i = 1 ; i <= n ; ++i )
{
cin>>dmd[i] ; gh.ins(m + i ,T , dmd[i], 0) ;
}
for( i = 1 ; i<=m ; ++i )
for( j = 1 ; j<=n ; ++j)
{
cin>>cost[i][j] ; gh.ins(i , j + m , inf , cost[i][j]) ;
}
int ret = gh.mcmf() ;
cout<<ret<<endl ;
gh.init(S, T , N);
for( i = 1 ; i<=m ; ++i ) gh.ins(S , i , sup[i], 0);
for( i = 1 ; i<=n ; ++i ) gh.ins(m + i ,T , dmd[i] , 0) ;
for( i = 1 ; i<=m ;++i)
for( j = 1; j<=n ;++j )
gh.ins(i , m + j , inf , - cost[i][j] ) ;
ret = gh.mcmf() ;
cout<<-ret<<endl ;
return 0 ;
}
分配问题
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std ;
const int maxn = 200 ;
const int maxe = maxn * maxn ;
const int inf = 1<<28 ;
struct node
{
int v , c , cost , next ;
} ;
struct network
{
int S , T , hd[maxn] , es , N ;
int vis[maxn] , d[maxn] , pos[maxn] , prev[maxn] ;
node e[maxe] ;
void init(int vS , int vT , int vcnt);
void ins(int u , int v ,int c ,int cost) ;
bool spfa() ;
int mcmf() ;
} ;
void network::init(int vS , int vT , int vcnt )
{
S = vS ; T = vT ; N = vcnt ;
es = 0 ; memset(hd , -1 ,sizeof(hd));
}
void network::ins(int u ,int v,int c ,int cost)
{
e[es].v = v , e[es].c = c , e[es].cost = cost , e[es].next = hd[u] ; hd[u] = es ++ ;
e[es].v = u , e[es].c = 0 , e[es].cost = -cost, e[es].next = hd[v] ; hd[v] = es ++ ;
}
bool network::spfa()
{
queue<int> Q ;
int u , v , i ;
for( i = 1 ; i<=N ; ++i ) vis[i] = 0 , d[i] = inf , prev[i] = -1 ;
vis[S] = 1 , Q.push(S) , d[S] = 0 ;
while(! Q.empty())
{
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for( i = hd[v] ; i!=-1 ; i = e[i].next )
{
u = e[i].v ;
if( e[i].c && d[u] > d[v] + e[i].cost )
{
d[u] = d[v] + e[i].cost ; prev[u] = v ; pos[u] = i ;
if( vis[u] == 0 ) vis[u] = 1 , Q.push(u);
}
}
}
return prev[T]!=-1 ;
}
int network::mcmf()
{
int take = 0 , del ,u ;
while(spfa())
{
del = inf ;
for( u = T ; u != S ; u = prev[u] ) del = min( del , e[pos[u]].c ) ;
for( u = T ; u != S ; u = prev[u] ) e[pos[u]].c -= del , e[pos[u]^1].c += del ;
take += del * d[T] ;
}
return take ;
}
int main()
{
network gh ;
int n , i , j , cost , S , T , mat[maxn][maxn] ;
cin>>n ; S = 2*n + 1 , T = 2*n + 2 ;
gh.init(S , T , T) ;
for( i = 1 ; i<=n ;++i )
{
gh.ins(S , i ,1 , 0 ) ;
gh.ins(n + i , T , 1 , 0 ) ;
}
for( i = 1 ; i<=n ; ++ i )
for( j = 1 ; j<=n ; ++j )
{
cin>>mat[i][j] ; gh.ins(i , j + n , 1 , mat[i][j] ) ;
}
int ret = gh.mcmf() ;
cout<<ret<<endl ;
gh.init(S , T , T) ;
for( i = 1 ; i<=n ;++i )
{
gh.ins(S , i ,1 , 0) ; gh.ins(n + i ,T ,1, 0) ;
}
for( i = 1 ;i<=n; ++i )
for( j = 1 ; j<=n ; ++j )
gh.ins(i , j+n , 1, -mat[i][j]) ;
ret = gh.mcmf() ;
cout<<-ret<<endl ;
return 0 ;
}
负载平衡问题
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std ;
const int maxn = 110 ;
const int maxe = maxn * maxn ;
const int inf = 1<<28 ;
struct node
{
int v , c , cost , next ;
} ;
struct network
{
int S ,T , N , hd[maxn] , es ;
int vis[maxn] , prev[maxn] , pos[maxn] , d[maxn] ;
node e[maxe] ;
void init(int vS , int vT , int vN ) ;
void ins(int u ,int v ,int c ,int cost) ;
bool spfa() ;
int mcmf() ;
} ;
void network::init(int vS ,int vT ,int vN)
{
S = vS , T =vT , N = vN ;
es = 0 , memset(hd , -1,sizeof(hd)) ;
}
void network::ins(int u ,int v,int c,int cost)
{
e[es].v = v , e[es].c = c, e[es].cost =cost ,e[es].next = hd[u] , hd[u] = es ++ ;
e[es].v = u , e[es].c = 0, e[es].cost =-cost,e[es].next = hd[v] , hd[v] = es ++ ;
}
bool network::spfa()
{
int u , v , i ; queue<int> Q ;
for( i = 1 ; i<=N ; ++i ) vis[i] = 0 , prev[i]=-1 ,d[i] = inf ;
vis[S] = 1 , Q.push(S) , d[S] = 0 ;
while(!Q.empty() )
{
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for( i = hd[v] ; i!=-1 ; i=e[i].next )
{
u = e[i].v ;
if( e[i].c && d[u] > d[v] + e[i].cost )
{
d[u] = d[v] + e[i].cost ; prev[u] = v ; pos[u]=i ;
if(!vis[u]) vis[u]=1 ,Q.push(u) ;
}
}
}
return prev[T]!=-1 ;
}
int network::mcmf()
{
int take = 0 , del , u ;
while(spfa())
{
del = inf ;
for( u = T ; u!=S ; u=prev[u] ) del = min( del , e[pos[u]].c ) ;
for( u = T ; u!=S ; u=prev[u] ) e[pos[u]].c -= del , e[pos[u]^1].c += del ;
take += del * d[T] ;
}
return take ;
}
int main()
{
network gh ;
int n , w[maxn] , S ,T , N , ret , i , j , sum ;
cin>> n ; S = n + 1 , T = S + 1 , N = T ;
gh.init(S , T , N ) ;
for( i = 1 , sum = 0 ; i <=n ;++i ) cin>>w[i] , w[i] *= n , sum += w[i] ;
sum /=n ;
for( i = 1 ; i<=n ; ++i )
if( sum >= w[i] )
gh.ins(S , i , sum - w[i] , 0 ) ;
else
gh.ins(i , T , w[i]-sum , 0 ) ;
for( i = 1 ; i<n ;++i )
gh.ins(i , i + 1, inf , 1 ) , gh.ins(i + 1, i , inf , 1) ;
gh.ins(n , 1 , inf , 1 ) ; gh.ins(1 , n , inf , 1 ) ;
ret = gh.mcmf() ;
cout<< ret/n <<endl ;
return 0 ;
}
深海机器人问题
最长k可重区间集问题
#include<iostream>
#include<queue>
#include<set>
#include<vector>
using namespace std ;
const int INF = 1<<29 ;
const int MaxSeg = 505 ;
const int MaxPnt = 2*MaxSeg ;
const int maxn = 2*(MaxPnt + 5) ;
const int maxe = 10*maxn ;
struct node{
int x , y , c , cost , next ;
};
node e[maxe] ;
int S , T , N , es , hd[maxn] ;
int dist[maxn] , vis[maxn] , ps[maxn] , prev[maxn] ;
int l[MaxSeg] , r[MaxSeg] , sgnt , K ;
set<int> ch ;
vector<int> vec ;
void ins(int x ,int y ,int c ,int cost){
e[es].x = x , e[es].y = y , e[es].c = c , e[es].cost = cost , e[es].next = hd[x] , hd[x] = es ++ ;
e[es].x = y , e[es].y = x , e[es].c = 0 , e[es].cost =-cost , e[es].next = hd[y] , hd[y] = es ++ ;
}
bool spfa(){
int i , u , v ;
queue<int> Q ;
for(i = 0 ; i <= N ; ++i) dist[i] = INF , vis[i] = 0 , prev[i] = -1 ;
dist[S] = 0 ; vis[S] = 1 ; Q.push(S) ;
while(!Q.empty()){
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for(i = hd[v] ; i!=-1 ; i=e[i].next){
u = e[i].y ;
if( e[i].c && dist[u] > dist[v] + e[i].cost){
dist[u] = dist[v] + e[i].cost ; prev[u] = v ; ps[u] = i ;
if(vis[u] == 0 )
vis[u] = 1 , Q.push(u) ;
}
}
}
return prev[T]!=-1 ;
}
int mcmf(){
int del , v , u , res = 0 ;
while(spfa()){
del = INF ;
for(v = T ; v!=S ; v = prev[v]) del = min(del , e[ps[v]].c) ;
for(v = T ; v!=S ; v = prev[v])
e[ps[v]].c -= del , e[ps[v]^1].c += del ;
res += del * dist[T] ;
}
return res ;
}
void readin(){
int i ;
set<int>::iterator it ;
ch.clear() ; vec.clear();
scanf("%d%d",&sgnt ,&K);
for(i = 0 ; i < sgnt ; ++i){
scanf("%d%d",&l[i] , &r[i]) ;
ch.insert(l[i]);
ch.insert(r[i]);
}
for(it = ch.begin() ; it!=ch.end() ; it++)
vec.push_back(*it);
}
int bbs(int x){
int mid , i , low = 0 , up = vec.size() - 1 ;
while(low <= up){
mid = (low + up)/2 ;
if(x == vec[mid]) return mid + 1;
if(x < vec[mid])
up = mid - 1 ;
else
low = mid + 1 ;
}
return 0 ;
}
int work() {
int i , j , k , low , up , ret ;
es = 0 ; memset(hd , -1 ,sizeof(hd));
S = vec.size() + 1 ; T = vec.size() + 2 ; N = T ;
ins(S , 1 , K , 0 ) ; ins(vec.size() , T , K , 0) ;
for(i = 1 ; i < vec.size() ; ++ i)
ins(i , i + 1 , K , 0 ) ;
for(i = 0 ; i < sgnt ; ++ i){
low = bbs(l[i]); up = bbs(r[i]) ;
ins(low , up , 1 , l[i] - r[i] ) ;
}
ret = mcmf() ;
return ret ;
}
int main(){
readin() ;
printf("%d\n",-work()) ;
return 0 ;
}
最长k可重线段集问题
火星探险问题
#include<iostream>
#include<queue>
using namespace std ;
const int grid = 40 ;
const int maxn = 2*grid*grid ;
const int maxe = 5 * maxn ;
const int INF = 1<<29 ;
struct node{
int y , c , cost ,next ;
};
node e[maxe] ;
int es , hd[maxn] , S ,T , N ;
int vis[maxn] , d[maxn] , ps[maxn] , prev[maxn] ;
int car , row , col , bd[grid][grid];
void ins(int x ,int y ,int c ,int cost ){
e[es].y = y , e[es].c = c, e[es].cost = cost , e[es].next = hd[x] , hd[x] = es ++ ;
e[es].y = x , e[es].c = 0, e[es].cost =-cost , e[es].next = hd[y] , hd[y] = es ++ ;
}
inline int V(int x ,int y) {
return x * col + y + 1;
}
inline bool out(int x,int y){
return x<0 || y<0 || x>=row || y>=col ;
}
bool spfa(){
queue<int> Q ;
int i , v , u ;
for(i = 0 ; i <= N ; ++i) d[i] = INF , vis[i] = 0 , prev[i] = -1 ;
d[S] = 0 ; vis[S] = 1 ; Q.push(S) ;
while(!Q.empty()){
v = Q.front() ; Q.pop() ;
for(i = hd[v] ; i!=-1 ; i=e[i].next){
u = e[i].y ;
if(e[i].c && d[u] > d[v] + e[i].cost){
d[u] = d[v] + e[i].cost ; prev[u] = v ; ps[u] = i ;
if(vis[u] == 0)
vis[u] = 1 , Q.push(u) ;
}
}
}
return prev[T]!=-1 ;
}
int MCMF(){
int res = 0 , del , i , v ;
while(spfa()){
del = INF ;
for(v = T ; v!=S ; v=prev[v]) del = min(del , e[ps[v]].c) ;
for(v = T ; v!=S ; v=prev[v])
e[ps[v]].c -= del , e[ps[v]^1].c += del ;
res += del * d[T] ;
}
return res ;
}
int work(){
int i , j , cnt = 0 , idx = 0;
scanf("%d%d%d",&car,&col,&row);
for(i = 0 ; i < row ; ++i)
for(j = 0 ; j < col ; ++j){
scanf("%d",&bd[i][j]);
if(bd[i][j] == 1)
cnt ++ ;
}
S = V(row-1,col-1) + cnt + 1 ; T = S + 1 ; N = T ;
es = 0 ; memset(hd , -1 ,sizeof(hd)) ;
ins(S , V(1,1) , car , 0 ) ; ins(V(row-1,col-1) , T , car , 0) ;
for(i = 0 ; i < row ; ++ i)
for(j = 0 ; j < col ; ++j)
if( bd[i][j]!=1 ){
if(!out(i+1,j) && bd[i+1][j]!=1 )
ins(V(i,j) , V(i+1,j) , INF , 0 ) ;
if(!out(i,j+1) && bd[i][j+1]!=1 )
ins(V(i,j) , V(i,j+1) , INF , 0 );
if( bd[i][j] == 2 ){
idx ++ ;
int vertex = V(row - 1 , col - 1) + idx ;
ins(V(i,j) , vertex , 1 , -1 ) ;
if(!out(i+1,j) && bd[i+1][j]!=1 )
ins(vertex , V(i+1,j) , 1 , 0 ) ;
if(!out(i,j+1) && bd[i][j+1]!=1 )
ins(vertex , V(i,j+1) , 1 , 0 ) ;
}
}
return -MCMF() ;
}
int main(){
printf("%d\n",work()) ;
return 0 ;
}
骑士共存问题
#include<iostream>
#include<memory.h>
#include<algorithm>
using namespace std ;
const int grid = 201;
const int maxn = grid * grid ;
const int maxe = maxn * 16;
const int inf = 1<<30 ;
int n , m ;
int dx[]={2,1,-1,-2,-2,-1,1,2} , dy[]={1,2,2,1,-1,-2,-2,-1} ;
int bd[grid][grid] ;
inline bool out(int x,int y)
{ return x < 0 || y < 0 || x >=n || y>=n ; }
struct node
{
int x,y,c,next ;
};
int S ,T ,N , es ,hd[maxn] ;
int cur[maxn] , ps[maxn] , dep[maxn] ;
node e[maxe] ;
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 dinic()
{
int i ,j , u ,v , k , tr , f, r , maxf = 0 , top ;
while(1)
{
f = r = 0 ; memset(dep , -1 ,sizeof(dep));
ps[r++] = S , dep[S] = 0 ;
while(f!=r)
{
v = ps[f++] ;
for(i = hd[v] ; i !=-1 ; i=e[i].next)
{
u = e[i].y ;
if(e[i].c && dep[u] == -1)
dep[u] = dep[v] + 1 , ps[r++] = u ;
}
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(k = 0 , tr = inf ; k < top ; ++ k)
if(e[ps[k]].c < tr ) tr = e[ps[k]].c , f = k ;
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[i]+1 == dep[ e[j].y ]) 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 ;
}
int main()
{
int vS , vT , vN , i , j , x, y , k , vx ,vy;
scanf("%d%d",&n,&m);
S = n*n + 1 , T = S + 1 , N = T ;
es = 0 ; memset(hd, -1 ,sizeof(hd)); memset(bd, 0 ,sizeof(bd));
for(i = 0 ; i<m ;++i)
scanf("%d%d",&x,&y) , bd[--x][--y] = 1 ;
vx = vy = 0 ;
for(i = 0 ; i < n ; ++i)
for(j = 0 ;j < n ; ++j)
if(!bd[i][j])
{
if( (i+j)%2 == 0 )
ins(S , i*n+j+1 , 1) , vx ++ ;
else
ins(i*n+j+1,T ,1) , vy ++ ;
}
for(i = 0 ;i<n; ++i)
for(j = 0 ; j<n ;++j)
if(!bd[i][j] && (i+j)%2==0)
for(k = 0 ;k<8;++k)
{
x=i+dx[k],y=j+dy[k];
if(out(x,y) || bd[x][y]) continue;
ins(i*n+j+1,x*n+y+1,inf);
}
printf("%d\n",vx+vy-dinic());
return 0 ;
}
终于贴完了！