【BZOJ 4443】[Scoi2015] 小凸玩矩阵

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4443
数据生成器:http://paste.ubuntu.com/23621596/
神犇题解:http://krydom.com/bzoj4443/

题解

考虑最值的话,肯定想到二分
又因为每行/每列只能选一个
那就是二分图匹配辣!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500 + 9;
const int M = 500000;
const int INF = 1e9;

int head[N],to[M],nxt[M],flow[M],cur[N],dis[N],TT;
int n,m,K,S,T,val[N/2][N/2],tot,TMP[M];
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = 1;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS() {
	memset(dis,60,sizeof(dis));
	dis[S] = 0; que.push(S);
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + 1 && flow[i]) {
				dis[to[i]] = dis[w] + 1;
				que.push(to[i]);
			}
		}
	}
	
	return dis[T] < 1e8;
}

int DFS(int w, int v) {
	if (w == T) {
		return v;
  	} else {
		int ret = 0;
		for (int &i=cur[w];i;i=nxt[i]) {
			if (dis[to[i]] == dis[w] + 1 && flow[i]) {
				int tmp = DFS(to[i], min(v, flow[i]));
				v -= tmp; ret += tmp;
				flow[i] -= tmp; flow[i^1] += tmp;
				if (!v) break;
			}
		}
		return ret;  	
	}
}

inline int Dinic() {
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	} 
	return ret;
}

inline bool judge(int sta) {
	memset(head,0,sizeof(head));
	TT = 1; S = 0; T = N - 1;
	for (int i=1;i<=n;i++) {
		Add_Edge(S,i);
		for (int j=1;j<=m;j++) {
			if (val[i][j] <= sta) {
				Add_Edge(i,n+j);
			}
		}
	}
	for (int i=1;i<=m;i++) 
		Add_Edge(n+i,T);
	return Dinic() >= n - K + 1;
}

int main(){
	n = read(); m = read(); K = read();
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			val[i][j] = TMP[++tot] = read();
		}
	}
	sort(TMP+1, TMP+1+tot);
	tot = unique(TMP+1, TMP+1+tot) - TMP - 1;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			val[i][j] = lower_bound(TMP+1, TMP+1+tot, val[i][j]) - TMP;
		}
	}
	
	int l=1, r=tot, mid, vout=0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) r = mid-1, vout = mid;
		else l = mid + 1;
	}
	printf("%d\n",TMP[vout]);
	return 0;
}

【BZOJ 1066】[SCOI2007] 蜥蜴

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1066

喜闻乐见大水题!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int L = 25;
const int N = L*L*2+9;
const int M = N*100;
const int INF = 10000000;

int nxt[M],to[M],flow[M],head[N],dis[N],cur[N];
int m,n,d,mat[L][L],vout,S,T;
char pat[N]; queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

#define id(x,y,ty) ((x)+((y)-1)*n+(ty)*m*n)
inline void Add_Edge(int u, int v, int f){
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(S);
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
			dis[to[i]] = dis[w] + 1, que.push(to[i]);
	}
	
	return ~dis[T];
}

int DFS(int w, int f) {
	if (w == T) return f;
	else {
		int ret = 0;
		for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
			int tmp = DFS(to[i], min(f, flow[i]));
			ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp;
			if (!f) break;
		}
		return ret;
	}
}

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

int main(){
	m = read(); n = read(); d = read(); S = 0; T = N-1;
	for (int j=1;j<=m;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) mat[i][j] = pat[i] - '0';
		for (int i=1;i<=n;i++) if (mat[i][j]) Add_Edge(id(i,j,0),id(i,j,1),mat[i][j]);
	}
	for (int j=1;j<=m;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) if (pat[i] == 'L') Add_Edge(S,id(i,j,0),1), vout++;
	}
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if (mat[i][j]) {
		if (min(min(i,n-i+1),min(j,m-j+1)) <= d) Add_Edge(id(i,j,1),T,INF);
		for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) 
			if (mat[x][y] && abs(x-i)+abs(y-j) <= d) Add_Edge(id(i,j,1),id(x,y,0),INF);
	}
	vout -= Dinic();
	printf("%d\n",vout);
	return 0; 
}

【BZOJ 4625】[BeiJing2016] 水晶

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4625
数据生成器:http://paste.ubuntu.com/23154162/

这个题目网上为什么搜不到题解QAQ
那我就来撸一份题解吧 = ̄ω ̄=

我们将六边形按照 (x+y+z)%3 == 0/1/2 来分类(染色)
不难发现,会变成这个样子:
486456445
之后,我们发现:两种共振一定是三个不同颜色的点产生的
于是把两种共振合起来考虑
因为我们必须任意三个中至少删一个,于是考虑最小割模型
将%3=1的点和S连一起,%3=2的和T连一起,%3=0的拆成两个点
现在产生共振的话,就连在一起。
这样的话,刚好符合题目的要求,于是跑一跑Dinic即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500000+9;
const int M = 1000000+9;
const int SGZ = 4100+9;
const int INF = 100000000;

int n,mat[SGZ][SGZ],idx[SGZ][SGZ],S,T,vout;
int nxt[M],head[N],to[M],flow[M],dis[N],cur[N];
struct Point{int x,y,t,c;}p[N];
queue<int> que;

inline bool cmp(const Point &A, const Point &B) {return A.x == B.x && A.y == B.y;}
inline bool CMP(const Point &A, const Point &B) {return A.x < B.x || (A.x == B.x && A.y < B.y);}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	que.push(S); dis[S] = 0;
	
	while (!que.empty()) {
		int w = que.front(); que.pop(); 
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) 
			dis[to[i]] = dis[w] + 1, que.push(to[i]);
	}
	return ~dis[T];
}

int DFS(int w, int f) {
	if (w == T) return f;
	else {
		int ret = 0;
		for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
			int tmp = DFS(to[i], min(f,flow[i]));
			flow[i] -= tmp; flow[i^1] += tmp;
			f -= tmp; ret += tmp;
			if (!f)	break;		
		} 
		return ret;
	}
}	

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	} return ret;
}

inline void Add_Edge(int u, int v, int f){
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = f;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = 0;
}

int main(){
	n = read();
	for (int i=1,x,y,z,c;i<=n;i++) {
		x = read(); y = read(); z = read(); c = read(); 
		x += 2001 - z; y += 2001 - z; p[i].t = (x+y) % 3;  
		c *= ((x+y)%3)?10:11;	mat[x][y] += c; vout += c;
		p[i].x = x; p[i].y = y;
	} 
	sort(p+1,p+1+n,CMP); 
	n = unique(p+1,p+1+n,cmp) - p - 1; 
	S = n*2 + 1, T = n*2 + 2;
	for (int i=1;i<=n;i++) idx[p[i].x][p[i].y] = i, p[i].c = mat[p[i].x][p[i].y];
	for (int i=1;i<=n;i++) 
		if (p[i].t == 1) Add_Edge(S,i,p[i].c);
		else if (p[i].t == 2) Add_Edge(i,T,p[i].c);
		else Add_Edge(i,i+n,p[i].c);
	for (int i=1,x,y;i<=n;i++) if (!p[i].t) {
		x = p[i].x; y = p[i].y;
		if (idx[x+1][y]) Add_Edge(idx[x+1][y],i,INF);
		if (idx[x][y+1]) Add_Edge(idx[x][y+1],i,INF);
		if (idx[x-1][y-1]) Add_Edge(idx[x-1][y-1],i,INF);
		if (idx[x+1][y+1]) Add_Edge(i+n,idx[x+1][y+1],INF);
		if (idx[x][y-1]) Add_Edge(i+n,idx[x][y-1],INF);
		if (idx[x-1][y]) Add_Edge(i+n,idx[x-1][y],INF); 
	}
	vout -= Dinic();
	cout<<vout/10<<'.'<<vout%10;
	return 0;
}

至于怎样如何很自然地想到这样构图
我也不知道
R}AML}}{T7C5Y2FLTM`R%54
已经问了YYY,但他还没有回我QAQ

—– UPD 2016.9.10 —–
YYY告诉我,这货不是很常见的构图?
来源于多米诺骨牌模型?

—– UPD 2016.9.13 —–
刚好看到YYY提到的那一类题目了
http://acm.hit.edu.cn/hoj/problem/view?id=2713