6.19训练日记

P1129 [ZJOI2007] 矩阵游戏

链接 网格图是一个经典的二分图模型,在这题中.交换行列实际上就是交换节点的相对编号,但是对原本的边的连接情况仍然不变. 我们规定左部是行,右部是列. 比如说(1,3)上是1.对应着左部编号1连接右部编号3. 如果我们实行行变换,就是把这条对应的左部节点编号1情况换到另外一个节点的编号情况.比如交换行1与行2. 此时变为了(2,3)有1,对应编号2的点连接到右部编号3. 同理,如果交换列了,就是交换右部点的连接情况. 题目有解的情况是有n条这样的边. （1,1）,(2,2),(3,3). 既然我们从行列交换中发现,我们可以交换两个节点的相对编号来实现.行交换就是更改左部点的相对编号,列交换是更改右部的相对编号. 再仔细思考下,如果我们对于这个图含有一个完美匹配的时候,这个网格该是什么样的形状的. 就是存在一种方案,比如说n=3的时候 0 0 1 1 0 0 0 1 0 像这种,人为很容易地就能知道如何更改的情况. 把上面的图用二分图划出来,就会发现,只要通过行列交换,变换起始点与终点的编号,总是能构造出(1,1),(2,2)(3,3)这样的边. 所以,这个问题转化为求是否存在一个完美匹配. 跑网络流即可.

#include
using namespace std;
const int maxn = 400+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
struct Edge{
	int from,to,cap,flow;//起点,终点,容量,流量
};
struct Dicnic{
	int n,m,s,t;//点,边,源点,汇点
	vector edges;//边集
	vector G[maxn];
	bool vis[maxn];//bfs 使用的
	int d[maxn];//起点到i的距离,就是bfs得到的层次图,下次dfs沿着d走
	int cur[maxn];//当前弧优化使用
	void addEdge(int from,int to,int cap){
		edges.push_back({from,to,cap,0});
		edges.push_back({to,from,0,0});//反向边
		m = edges.size();
		G[from].push_back(m-2);G[to].push_back(m-1);
		//正边的编号都是偶数,反向边的编号都是奇数
	}
	bool bfs(){
		memset(vis,0,sizeof(vis));
		queue Q;Q.push(s);
		d[s]=0;vis[s]=true;
		while(!Q.empty()){
			int x = Q.front();Q.pop();
			for(auto v : G[x]){
				Edge &e = edges[v];//获得边的编号
				if(!vis[e.to]&&e.cap>e.flow){
					//只有未被访问过,而且位于残量网络中的弧才考虑
					vis[e.to]=1;
					d[e.to]=d[x]+1;Q.push(e.to);
				}
			}
		}
		return vis[t];
	}
        int dfs(int x,int a){
		//寻找增广路,a代表目前经过的路中,每个边剩余的流量
		if(x==t||a==0) return a;//到达终点/残量为0
		int flow = 0,f;
		for(int &i = cur[x];i0){
				//首先要按层次图走,然后当前增加流量要是增广路中流量最小的的
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;//正边加流量,反边减流量
				flow+=f;a-=f;
				if(a==0) break;
			}
		}
		return flow;
	}
	int Maxflow(int s,int t){
		this->s=s;this->t=t;
		int flow=0;
		while(bfs()){
			memset(cur,0,sizeof(cur));flow+=dfs(s,INF);
		}
		return flow;
	}
};
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		Dicnic g;
		int n;cin>>n;
		for(int i=1;iok;
				if(ok){
					g.addEdge(i,n+j,1);
				}
			}
		}
		//源点
		int s = 0,t=2*n+2;
		for(int i=1;il[i]>>r[i];
		dfs(1,0);
		coutval[i],ans=max(val[i],ans);
	for(int i=1;i>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	ans = max(ans,dp[1]);
//	for(auto v : G[1]){
//		ans = max(ans,dp[v]);
//	}
	cout