【BZOJ 1458】士兵占领

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

大体上同BZOJ_1711
具体来说,假设全部填上,于是要删尽量多的点
然后行放左边,列放右边,点拆开放中间

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

const int L = 100+9;
const int N = 50000+9;
const int M = 1000000;
const int INF = 1000000000;

int head[N],nxt[M],to[M],dis[N],cur[N],flow[M];
int n,m,X[L],Y[L],cx[L],cy[L],k,S,T,mat[L][L],vout;
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) (x+(y-1)*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(); k = read(); S = 0, T = N-1; vout = n*m;
	for (int i=1;i<=m;i++) Y[i] = read(), cy[i] = n;
	for (int i=1;i<=n;i++) X[i] = read(), cx[i] = m;
	for (int i=1,x,y;i<=k;i++) x = read(), y = read(), mat[x][y] = 1, cx[x]--, cy[y]--, vout--;
	for (int i=1;i<=m;i++) if (cy[i] < Y[i]) puts("JIONG!"), exit(0);
	for (int i=1;i<=n;i++) if (cx[i] < X[i]) puts("JIONG!"), exit(0);
	
	for (int i=1;i<=n;i++) Add_Edge(S,i,cx[i]-X[i]);
	for (int i=1;i<=m;i++) Add_Edge(n+i,T,cy[i]-Y[i]);
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if (!mat[i][j]) 
		Add_Edge(m+n+id(i,j),m+n+m+n+id(i,j),1),
		Add_Edge(i,m+n+id(i,j),1), Add_Edge(m+n+m+n+id(i,j),j+n,1);
	printf("%d\n",vout-Dinic());
	return 0;
}

【BZOJ 1711】[Usaco2007 Open] Dining吃饭

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

《网络流建模汇总》的例题
牛放中间,食物放左边,饮料放右边

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

const int N = 400+9;
const int M = 1000000;
const int INF = 1000000000;

int S,T,f,d,n,head[N],nxt[M],to[M],flow[M],dis[N],cur[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;
}

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(){
	n = read(); f = read(); d = read(); S = 0; T = N-1;
	for (int i=1;i<=f;i++) Add_Edge(S,i,1);
	for (int i=1;i<=d;i++) Add_Edge(i+f+n,T,1);
	for (int i=1;i<=n;i++) Add_Edge(f+i,f+n+d+i,1);
	for (int i=1,t1,t2;i<=n;i++) {
		t1 = read(); t2 = read(); 
		for (int j=1;j<=t1;j++) Add_Edge(read(),i+f,1);
		for (int j=1;j<=t2;j++) Add_Edge(i+f+n+d,read()+f+n,1);
	} printf("%d\n",Dinic());
	return 0;
}

【BZOJ 1189】[HNOI2007] 紧急疏散evacuate

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

这题还是很好想的,要么二分时间,要么时间上暴力
然而HZWER的做法是错误的,门那里肯定需要按时间拆点

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

const int N = 500000;
const int M = 2000000;
const int L = 30;
const int INF = 10000000;

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

#define id(x,y) ((x)+((y)-1)*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;
}

inline void search(int s){
	memset(dis,-1,sizeof(dis));
	que.push(s); dis[s] = 0; 
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		int x=w, y=0; while ((y+1)*n < w) y++; x -= y*n; y++;
		if (mat[x][y] == 1) Add_Edge(w,num[s][dis[w]],1);
		if (x - 1 >= 1 && !~dis[id(x-1,y)] && mat[x-1][y] == 1) que.push(id(x-1,y)), dis[id(x-1,y)] = dis[w] + 1;
		if (x + 1 <= n && !~dis[id(x+1,y)] && mat[x+1][y] == 1) que.push(id(x+1,y)), dis[id(x+1,y)] = dis[w] + 1;
		if (y - 1 >= 1 && !~dis[id(x,y-1)] && mat[x][y-1] == 1) que.push(id(x,y-1)), dis[id(x,y-1)] = dis[w] + 1;
		if (y + 1 <= m && !~dis[id(x,y+1)] && mat[x][y+1] == 1) que.push(id(x,y+1)), dis[id(x,y+1)] = dis[w] + 1;
	}
}

int main(){
	cin>>m>>n; S = 0; T = N-1; nod_cnt = n*m;
	for (int j=1;j<=m;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) 
			if (pat[i] == 'X') mat[i][j] = 2;
			else if (pat[i] == '.') mat[i][j] = 1, vout++, Add_Edge(S,id(i,j),1);
			else dor.push_back(id(i,j));
	} 
	for (int i=0,lim=dor.size();i<lim;i++) for (int k=1;k<=n*m;k++) num[dor[i]].push_back(++nod_cnt);
	for (int i=0,lim=dor.size();i<lim;i++) search(dor[i]);
	for (int k=0,ret=0;k<n*m;k++) {
		ret += Dinic();
		if (ret == vout) printf("%d\n",k), exit(0);
		for (int i=0,lim=dor.size();i<lim;i++) 
			Add_Edge(num[dor[i]][k],num[dor[i]][k+1],INF),
			Add_Edge(num[dor[i]][k+1],T,1);
	} puts("impossible");
	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; 
}