lp2774 方格取数问题

这是一道最小割转最大流的例题。
首先,我们发现,这一题要求我们求的是所取和。然后容易知道,所取和等于总和减去舍弃和。
故而,我们要使得所取和最大,就只需要使得舍弃和最小。
尝试用所取和来建图并且跑最大流,发现,它并不是那么容易地建成一个可靠的图。
正难则反,我们考虑怎么样才能让舍弃和最小。
于是尝试用舍弃和最小来建图并且跑最小割。观察题目的性质我们发现,所有的坐标和的奇偶性相同的方格,永远是互不影响的。
这启发我们建一个二分图。
我们不妨将奇点建在左侧,偶点建在右侧。然后从源点向奇点连容量为数值的边;从偶点向汇点连容量为数值的边。
于是,很显然,当我们割掉任何一条边的时候,就意味着相应的点是不取的。
接着我们将相邻的黑白点连容量为无穷大的边,这意味着这两个点之间至少有一个不能取。
然后跑最大流得到最小割即可。

#include<iostream>
#include<cstdio>
#include<queue>


const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f; 

inline int Min(int A,int B){
	return A<B?A:B;
}


struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[40005],et=-1;
int dep[40005],nw[40005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int n,m,s,t;

inline int calc(int X,int Y){
	return (X-1)*m+Y;
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
			
		}
	}
	return cnt;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,cnt=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&x);
			cnt+=x;
			if((i+j)&1){
				add(s,calc(i,j),x);
				if(i+1<=n){
					add(calc(i,j),calc(i+1,j),VERYBIG);
				}
				if(i-1>=1){
					add(calc(i,j),calc(i-1,j),VERYBIG);
				}
				if(j+1<=m){
					add(calc(i,j),calc(i,j+1),VERYBIG);
				}
				if(j-1>=1){
					add(calc(i,j),calc(i,j-1),VERYBIG);	
				}
			}else{
				add(calc(i,j),t,x);
			} 
		}
	}
	printf("%d\n",cnt-dinic());
}

int main(){
	init();
	return 0;
}

lp2766 网络流24题-最长不下降子序列问题

这是一道看起来很简单的麻题。
很显然可以发现第一问就是直接n^2DP求一个答案。
第二问模拟寻找最长不下降子序列的过程。
第三问改几条边再跑一遍。
但是要注意很多很多细节。
比如说,建模的时候应该反着建。
再比如说,对于最长长度只有1的情况应当格外注意,因为这可能会导致各种错误。
写起来还是有点烦心的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

const int INF=0x3f3f3f3f;
const int BIG=19260817;
inline int Min(int A,int B){
	return A<B?A:B;
}

inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[250005];
int h[2005],et=-1;

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int dep[2005],nw[2005],a[505];
int n,s,t,len;
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF,nw[i]=h[i];
	}
	dep[s]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
//	for(int i=1;i<=t;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	return dep[t]^INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
		}
	}
	return cnt;
}
int f[505];
inline void slv1(){
	for(int i=1;i<=n;++i){
		f[i]=1;
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]){
				f[i]=Max(f[i],f[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,f[i]);
	}
	len=ans;
	printf("%d\n",ans);
}

inline int dinic(){
	int RT=0;
	while(bfs()){
		RT+=dfs(s,INF);
	}
	return RT;
}

inline void slv2(){
	s=2*n+1,t=2*n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	et=-1;
	for(int i=1;i<=n;++i){
		if(f[i]==len){
			add(i+n,t,1);
		}
		if(f[i]==1){
			add(s,i,1);
		}
		add(i,i+n,1);
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]&&f[j]+1==f[i]){
				add(j+n,i,1);
			}
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
	add(1,n+1,BIG),add(s,1,BIG);
	if(f[n]==len){
		add(n,2*n,BIG),add(2*n,t,BIG);
	}
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	slv1();
	slv2();
}
int main(){
	init();
	return 0;
}

lp2764 网络流24题-最小路径覆盖问题


(其实建图方法已经写在题目里了。)
(这一题是一道匈牙利的裸题,考场上二分图最大匹配仍然建议使用匈牙利(因为在实现复杂度上有巨大优势),我纯粹练一下当前弧优化Dinic。)
首先有一个定理。将一张有向图上的每一个点都拆点成入点和出点,连边后形成一张二分图,那么原图的最小路径覆盖,就是顶点数减去这张二分图的最大匹配。
考虑感性地证明这个定理。
每一次匹配,事实上就意味着,一条路径可以额外走过一个点。这样就减少了一个路径覆盖。
所以,当匹配次数最大的时候,路径覆盖数就最小了。
答案用并查集处理一下输出。


#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[2005],et=-1;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}
int dep[2005],nw[2005],f[2005];
int n,m,s,t;

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i; 
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

inline int fnd(int X){
	for(int i=h[X+n];i>=0;i=e[i].nxt){
		if(1<=e[i].v&&e[i].v<=n){
			if(e[i].w){
				return e[i].v;
			}
		}
	}
	return X;
}
inline int fa(int X){
	return f[X]^X?f[X]=fa(f[X]):X;
}
inline void prnt(int X){
	for(int i=h[X];i>=0;i=e[i].nxt){
		if((n+1)<=e[i].v&&e[i].v<=(n<<1)&&!e[i].w){
			printf("%d ",e[i].v-n
			);
			prnt(e[i].v-n);
			return;
		}
	}
}
bool vis[2005];
void init(){
	scanf("%d%d",&n,&m);
	s=(n<<1)+1,t=(n<<1)+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		add(s,i,1);
		add(n+i,t,1);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,n+v,1);
	}
	int ans=n;
	while(bfs()){
		ans-=dfs(s,INF);
	}
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=1;i<=n;++i){
		f[i]=fnd(i);
	}
	for(int i=1;i<=n;++i){
		fa(i);
	}
	for(int i=1;i<=n;++i){
		if(f[i]==i){
			printf("%d ",i);
			prnt(i);
			puts("");
		}
	}
	printf("%d\n",ans); 
}

int main(){
	init();
	return 0;
}

lp2763 网络流24题-试题库问题

对于这一题,我们建三层的边来描述题目中的约束。
对于每道题建一个点,源点连一条容量为1的边到每一个点,表示每道题最多只能被选取一次。
对于每个种类建一个点,每一个点连一条容量为1的边到它所属的所有类,表示它仅可以被作为这个类来选取。
每个种类连一条容量为这个种类需要的选取次数的边到汇点,表示这个种类最多需要被选取的次数。
然后,跑一遍当前弧优化Dinic最大流,如果需要选取的总题数都能选取到,流量就等于需要选取的总题数。
当然也可以大力拆点跑二分图匹配,不过那样似乎更难写的样子。

#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[2005],et=-1;
int dep[2005],nw[2005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0); 
}

int n,m,s,t,Sans=0,tot; 

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
} 
//V表示从源点到当前路径上的剩余流量,cnt表示这个点向后流了多少流量。 
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				V-=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

void init(){
	scanf("%d%d",&m,&n);
	s=m+n+1,t=m+n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
//	注意初始化。 
	int p,x;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		Sans+=x;
		add(n+i,t,x);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p);
		add(s,i,1);
		for(int j=1;j<=p;++j){
			scanf("%d",&x);
			add(i,n+x,1);
//			注意哈希。 
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
		printf("%d\n",ans); 
	}
	if(ans<Sans){
		puts("No solution!");
		return;
	}
	for(int i=1;i<=m;++i){
		printf("%d: ",i);
		for(int j=h[n+i];j;j=e[j].nxt){
			if((j&1)&&(e[j].w==1)&&(e[j].v!=t)){
				printf("%d ",e[j].v);
			}
		}
		puts("");
	}
}

int main(){
	init();
	return 0;
}

lp3355 网络流24题-骑士共存问题

首先我们观察这道题。
暴力地状压DP或者之类的操作显然会MLE/TLE。
我们发现,横坐标和纵坐标相加的和的奇偶性相同的格子永远不可能互相攻击到。
故而我们考虑建一张二分图。将横纵坐标的和的奇偶性不同的格子分别放在左右边,然后在能相互攻击到的点之间连边。依据题意,不能相互攻击到,所以答案即是这张图的最大独立集。

二分图最大独立集应当如何求得?我们有一个定理:一张二分图的最大独立集的大小等同于顶点数它的最大匹配的数量。
我们考虑感性地证明这个定理。
很容易可以发现,两个点不能被同时选取,当且仅当它们之间有连边。
又因为,有连边的两个点必然是属于二分图的两端的。
故而,如果有两个点不能被同时选取,它们必然可以构成一个匹配。
对于二分图上的最大匹配,所有没有被匹配的点都可以被选取。这非常的显然,因为没有被匹配到的点之间必然没有连边。如果有连边,那么就可以增加匹配,与最大匹配矛盾。
而,对于每一个匹配,都可以选取一组匹配中的一个点。这是因为,对于一些连通的匹配,它们有且仅有一个部分(左边或者右边)会和未匹配点连接。
这也是很显然的,因为如果不是这样的话,就存在一条新的增广路径,就可以得到更多的匹配了。
注意:坐标如何哈希成一个数字。

#include<iostream>
#include<cstdio>

const int dx[8]={-2,-1,1,2,-2,-1,1,2};
const int dy[8]={1,2,2,1,-1,-2,-2,-1}; 

struct ee{
	int v;
	int nxt;
}e[160005];
int h[40005],et=0;

inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et; 
}

bool vis[40005],mp[205][205];
int n=0,m=0,usd[40005];

inline int calc(int X,int Y){
	return (X-1)*n+Y;
//	注意坐标哈希成数字的方式。 
}

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			vis[e[i].v]=1;
			if(!usd[e[i].v]||dfs(usd[e[i].v])){
				usd[e[i].v]=X;
				return 1;
			}
		}
	}
	return 0;
}
int st[40005],tp=0;
char out[205][205];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			mp[i][j]=0;
			usd[calc(i,j)]=0;
			out[i][j]='O';
		}
	}
	int x,y;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			printf("[%d %d] ",i,j);
			if(mp[i][j]||((i+j)&1)){
//				注意不是每次跳2而是判奇偶性。 
				continue;
			}
			st[++tp]=calc(i,j);
			out[i][j]='@'; 
			//注意有障碍的不仅是结束点,还有出发点。 
			for(int k=0;k<8;++k){
				x=i+dx[k],y=j+dy[k];
				if(x<=0||y<=0||x>n||y>n||mp[x][y]){
					continue;
				}
				out[x][y]='X';
				add(calc(i,j),calc(x,y));
			}
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=n;++j){
//			putchar(out[i][j]);
//		}
//		puts("");
//	}
	int ans=n*n-m;
//	减去被挖掉的点 
	for(int i=1;i<=tp;++i){
		for(int j=1;j<=n*n;++j){
			vis[j]=0;
		}
		ans-=dfs(st[i]);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
} 

lp2756 网络流24题-飞行员配对方案问题

这是一个裸的配对问题。
我们可以建成一个二分图然后跑匈牙利。

#include<iostream>
#include<cstdio>
bool mp[105][105],vis[105];
int n,m,usd[105];

inline int dfs(int X){
    for(int i=1;i<=m;++i){
        if(!mp[X][i]){
            continue;
        }
        if(!vis[i]){
            vis[i]=1;
            if(!usd[i]||dfs(usd[i])){
                usd[i]=X;
                return 1;
            }
        }
    }
    return 0;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            mp[i][j]=mp[j][i]=0;
        }
    }
    int x=1,y=1;
    //你绝对想不到的错误——x,y没有初始化,导致判断它们的初始值的时候出现错误。 
    while(x>=0&&y>=0){
        scanf("%d%d",&x,&y);
        y-=n;
        mp[x][y]=1;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            vis[j]=0;
        }
//        for(int j=1;j<=m;++j){
//        	printf("%d ",usd[j]);
//		}
//		puts("");
        ans+=(int)dfs(i);
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;++i){
        if(usd[i]){
            printf("%d %d\n",usd[i],i+n);
            //注意这里要将编号还原。并且别输出反了。 
        }
    } 
}

int main(){
    init();
    return 0;
}