网络流 – Page 3 – Qizy's Database

【BZOJ 2127】happiness

2016年9月17日2016年9月17日 Qizy 26 Comments

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2127
数据传送门：http://pan.baidu.com/s/1c1Ldkp6

这题的输入数据我已无力吐槽……
为此wa了两个小时

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

const int L = 100+9;
const int N = 10000+9;
const int M = 500000+9;
const int INF = 100000000;

int head[N],nxt[M],to[M],flow[M],n,m,vout,wen[L][L],li[L][L];
int dis[N],cur[N],S,T; 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(i,j) ((i)+((j)-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] = f;
}

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(); S = 0; T = N-1;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), wen[i][j] += tmp*2;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) vout += (tmp = read()), li[i][j] += tmp*2;
	for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), wen[i][j] += tmp, wen[i+1][j] += tmp;
	for (int i=1;i<n;i++) for (int j=1,tmp;j<=m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i+1,j),tmp), li[i][j] += tmp, li[i+1][j] += tmp;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), wen[i][j] += tmp, wen[i][j+1] += tmp;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<m;j++) tmp = read(), vout += tmp, Add_Edge(id(i,j),id(i,j+1),tmp), li[i][j] += tmp, li[i][j+1] += tmp;
	for (int i=1;i<=n;i++) for (int j=1,tmp;j<=m;j++) Add_Edge(S,id(i,j),wen[i][j]), Add_Edge(id(i,j),T,li[i][j]);
	printf("%d\n",vout-Dinic()/2);
	return 0;
}

【BZOJ 2132】圈地计划

2016年9月17日2016年9月17日 Qizy 25 Comments

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

可以说是最经典的一种最小割建模了吧！
看一看这张图片就能知道他的重要性了：

然而做题的时候，只能确定是染色后转二分图，并没有确定该如何建图QAQ
题解的话，让我们召唤Menci:https://oi.men.ci/bzoj-2132/

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

const int L = 100+9;
const int N = L*L+9;
const int M = N*15;
const int INF = 1000000000;

int head[N],nxt[M],to[M],flow[M],n,m,A[L][L],B[L][L],C[L][L],vout;
int S,T,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;
}

#define id(i,j) (i+((j)-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] = f;
}

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(); S = 0; T = N-1;
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (A[i][j] = read());
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) vout += (B[i][j] = read());
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) C[i][j] = read();
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
		if (i+j & 1) Add_Edge(S,id(i,j),A[i][j]), Add_Edge(id(i,j),T,B[i][j]);
		else Add_Edge(S,id(i,j),B[i][j]), Add_Edge(id(i,j),T,A[i][j]);
		if (j > 1 && i+j&1) Add_Edge(id(i,j),id(i,j-1),C[i][j]+C[i][j-1]), vout += C[i][j]+C[i][j-1];
		if (i > 1 && i+j&1) Add_Edge(id(i,j),id(i-1,j),C[i][j]+C[i-1][j]), vout += C[i][j]+C[i-1][j];
		if (j < m && i+j&1) Add_Edge(id(i,j),id(i,j+1),C[i][j]+C[i][j+1]), vout += C[i][j]+C[i][j+1];
		if (i < n && i+j&1) Add_Edge(id(i,j),id(i+1,j),C[i][j]+C[i+1][j]), vout += C[i][j]+C[i+1][j];
	} printf("%d\n",vout-Dinic());
	return 0;
}

【BZOJ 3171】[Tjoi2013] 循环格

2016年9月17日2016年9月17日 Qizy 333 Comments

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

按照入度出度拆点，然后就是萌萌哒费用流啦！

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

const int N = 15*15*2+9;
const int M = N*10; 
const int INF = 100000000;

int head[N],nxt[M],to[M],cost[M],flow[M],n,m,dis[N],FLOW[N];
int ord[20],dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1},S,T,inq[N],sur[N];
char pat[20]; 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 int id(int x, int y, int ty) {
	static int SUM = n*m;
	if (!x) x = n; else if (x == n+1) x = 1;
	if (!y) y = m; else if (y == m+1) y = 1;
	return x+(y-1)*n+ty*SUM;
}

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

inline int SPFA() {
    memset(dis,127,sizeof(dis));
    memset(FLOW,0,sizeof(FLOW));
    que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
      
    while (!que.empty()) {
        int w = que.front(); que.pop(); inq[w] = 0;
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
            dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
            FLOW[to[i]] = min(FLOW[w], flow[i]);
            if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
        }
    } return FLOW[T];
}
  
inline int MCMF() {
    int ret = 0;
    for (int w=T,f;f=SPFA();w=T) 
        for (int t=sur[w];w!=S;t=sur[w]) 
            flow[t] -= f, flow[t^1] += f,
            ret += cost[t]*f, w = to[t^1];
    return ret;
}

int main(){
	m = read(); n = read(); S = 0; T = N-1;
	for (int j=1;j<=m;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) 
			if (pat[i] == 'R') ord[i] = 1; else if (pat[i] == 'D') ord[i] = 2;
			else if (pat[i] == 'L') ord[i] = 3; else ord[i] = 4;
		for (int i=1;i<=n;i++) {
			Add_Edge(S,id(i,j,0),1,0); Add_Edge(id(i,j,1),T,1,0);
			Add_Edge(id(i,j,0),id(i+dx[ord[i]],j+dy[ord[i]],1),1,0);
			for (int k=1;k<=4;k++) if (k != ord[i]) Add_Edge(id(i,j,0),id(i+dx[k],j+dy[k],1),1,1);
		}
	} printf("%d\n",MCMF());
	return 0;
}

【BZOJ 2768】[JLOI2010] 冠军调查

2016年9月17日2016年9月17日 Qizy 3 Comments

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

真·双倍经验
同BZOJ_1934

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

const int N = 300+9;
const int M = N*N*2;
const int INF = 10000000;

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

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(); m = read(); S = 0; T = n+1;
	for (int i=1;i<=n;i++) if (!read()) Add_Edge(S,i,1); else Add_Edge(i,T,1);
	for (int i=1,a,b;i<=m;i++) a = read(), b = read(), Add_Edge(b,a,1);
	printf("%d\n",Dinic()); 
	return 0;
}

【BZOJ 1934】[Shoi2007] Vote 善意的投票

2016年9月17日2017年7月4日 Qizy 3 Comments

解题报告

网上都说这题简单，然而我怎么一点都不觉得啊QAQ
做题的时候，认定是最小割，然而怎么都建不出图
一直想搞成二分图，然而一直搞不成

最后看了题解
感觉这题还是相当不错的！
先假设每一个人都按照原始意图进行了选择
然后再来最小化冲突
具体到建图，可以把赞同的连到S，不赞同的连到T
朋友之间连双向边，因为朋友可能会变卦

这么建图有一个非常形象的理解：
最后和S相连的就是最后赞同的，最后和T相连的就是否决的
那么对于S->T的一条路径：
要么冲突+1，即割掉朋友间的那条边
要么其中一人改变选择，即割掉两侧的边

Code

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

const int N = 300+9;
const int M = N*N*2;
const int INF = 10000000;

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

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(); m = read(); S = 0; T = n+1;
	for (int i=1;i<=n;i++) if (!read()) Add_Edge(S,i,1); else Add_Edge(i,T,1);
	for (int i=1,a,b;i<=m;i++) a = read(), b = read(), Add_Edge(b,a,1);
	printf("%d\n",Dinic()); 
	return 0;
}

—————————— UPD 2017.7.4 ——————————
好像这题是挺简单的

【BZOJ 1221】[HNOI2001] 软件开发

2016年9月16日2016年9月16日 Qizy Leave a comment

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

真·双倍经验

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000;
const int INF = 100000000;
 
int head[N],nxt[N],to[N],cost[N],flow[N],dis[N],inq[N];
int n,st,sc,ft,fc,arr[N],S,T,p,sur[N],FLOW[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,ty) ((x)*2+ty)
inline void Add_Edge(int u, int v, int f, int c) {
    static int TT = 1;
    to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
    to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}
 
inline int SPFA() {
    memset(dis,127,sizeof(dis));
    memset(FLOW,0,sizeof(FLOW));
    que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
     
    while (!que.empty()) {
        int w = que.front(); que.pop(); inq[w] = 0;
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
            dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
            FLOW[to[i]] = min(FLOW[w], flow[i]);
            if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
        }
    } return FLOW[T];
}
 
inline int MCMF() {
    int ret = 0;
    for (int w=T,f;f=SPFA();w=T) 
        for (int t=sur[w];w!=S;t=sur[w]) 
            flow[t] -= f, 
            flow[t^1] += f,
            ret += cost[t]*f, 
            w = to[t^1];
    return ret;
}
 
int main(){
    n = read(); ft = read()+1; st = read()+1; p = read(); fc = read(); sc = read(); S = 0; T = 1;
    for (int i=1;i<=n;i++) arr[i] = read();
    for (int i=1;i<=n;i++) Add_Edge(S,id(i,0),arr[i],0), Add_Edge(id(i,1),T,arr[i],0);
    for (int i=1;i<n;i++) Add_Edge(id(i,0),id(i+1,0),INF,0);
    for (int i=1;i<=n;i++) if (i + ft <= n) Add_Edge(id(i,0),id(i+ft,1),INF,fc);
    for (int i=1;i<=n;i++) if (i + st <= n) Add_Edge(id(i,0),id(i+st,1),INF,sc);
    for (int i=1;i<=n;i++) Add_Edge(S,id(i,1),INF,p);
    printf("%d\n",MCMF());
    return 0;
}

【COGS 741】[网络流24题] 负载平衡

2016年9月16日2016年9月16日 Qizy 1 Comment

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=741

虽然是“网络流24题”之一，然而可以O(n)搞
来来来，我们一起来推式子！
6541324587

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

const int N = 100+9;

int n,arr[N],sum,vout,sta;

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;
}

int main(){
	freopen("overload.in","r",stdin);
	freopen("overload.out","w",stdout);
	n = read(); 
	for (int i=1;i<=n;i++) sum += (arr[i] = read()); sum /= n;
	for (int i=1;i<=n;i++) arr[i] -= sum - arr[i-1];
	nth_element(arr+1,arr+n/2,arr+n); sta=arr[n/2];
	for (int i=1;i<=n;i++) vout += abs(arr[i]-sta);
	cout<<vout<<endl;  
	return 0;
}

感觉真的是好神奇啊！

【COGS 461】[网络流24题] 餐巾

2016年9月16日2016年9月16日 Qizy 25 Comments

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=461

建图方法是：
将每天的输入和输出拆点，建成二分图的样子
然后搞一搞，详见Sengxian’s Blog
之前直接建成时间线来跑，结果血wa
后来发现，那么建图根本没法保证每一天满流啊！

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

const int N = 10000;
const int INF = 100000000;

int head[N],nxt[N],to[N],cost[N],flow[N],dis[N],inq[N];
int n,st,sc,ft,fc,arr[N],S,T,p,sur[N],FLOW[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,ty) ((x)*2+ty)
inline void Add_Edge(int u, int v, int f, int c) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline int SPFA() {
	memset(dis,127,sizeof(dis));
	memset(FLOW,0,sizeof(FLOW));
	que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
	
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
			dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
			FLOW[to[i]] = min(FLOW[w], flow[i]);
			if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
		}
	} return FLOW[T];
}

inline int MCMF() {
	int ret = 0;
	for (int w=T,f;f=SPFA();w=T) 
		for (int t=sur[w];w!=S;t=sur[w]) 
			flow[t] -= f, 
			flow[t^1] += f,
			ret += cost[t]*f, 
			w = to[t^1];
	return ret;
}

int main(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	n = read(); S = 0; T = 1;
	for (int i=1;i<=n;i++) arr[i] = read();
	p = read(); ft = read(); fc = read(); st = read(); sc = read();
	for (int i=1;i<=n;i++) Add_Edge(S,id(i,0),arr[i],0), Add_Edge(id(i,1),T,arr[i],0);
	for (int i=1;i<n;i++) Add_Edge(id(i,0),id(i+1,0),INF,0);
	for (int i=1;i<=n;i++) if (i + ft <= n) Add_Edge(id(i,0),id(i+ft,1),INF,fc);
	for (int i=1;i<=n;i++) if (i + st <= n) Add_Edge(id(i,0),id(i+st,1),INF,sc);
	for (int i=1;i<=n;i++) Add_Edge(S,id(i,1),INF,p);
	printf("%d\n",MCMF());
	return 0;
}

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

2016年9月13日2016年9月17日 Qizy 25 Comments

题目传送门：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;
}

【COGS 728】[网络流24题] 最小路径覆盖问题

2016年9月13日2016年9月13日 Qizy 26 Comments

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=728

这个玩意，我们可以参考：https://oi.men.ci/cogs-728/
也可以参考：https://www.byvoid.com/blog/lpf24-3
这题我觉得可以想成是点的入读与出度之间相互匹配

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

const int N = 10000;
const int M = 100000;
const int INF = 1000000;

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

void print(int w) {
	vis[w] = 1; printf("%d ",w);
	for (int i=head[w];i;i=nxt[i]) if (!flow[i] && !vis[to[i]])
		{print(to[i]>n?to[i]-n:to[i]); break;}
}

int main(){
	freopen("path3.in","r",stdin);
	freopen("path3.out","w",stdout);
	vout = n = read(); m = read(); S = 0; T = N-1; vis[S] = vis[T] = 1;
	for (int i=1,u,v;i<=m;i++) u = read(), v = read(),	Add_Edge(u,v+n,1);
	for (int i=1;i<=n;i++) Add_Edge(S,i,1), Add_Edge(i+n,T,1);
	vout -= Dinic();
	for (int i=1,w;i<=n;i++) if (!vis[i])
		print(i), putchar('\n');
	printf("%d\n",vout);
	return 0;
}

值得一提的是，这题的SPJ居然对于文末回车敏感 (╯‵□′)╯︵┻━┻
害的老子调了一个小时 QAQ

【BZOJ 1877】[SDOI2009] 晨跑

2016年9月13日2016年9月13日 Qizy Leave a comment

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

喜闻乐见大水题！

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

const int N = 200*2+9;
const int M = 50000+9;
const int INF = 100000000;

int head[N],dis[N],nxt[M],cost[M],to[M],flow[M]; 
int n,m,S,T,F,C,inq[N],cur[N],sur[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,ty) ((x)+n*(ty))
inline void Add_Edge(int u, int v, int f, int c) {
	static int TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}

inline bool SPFA(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(S); inq[S] = 1; cur[S] = INF;
	
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=nxt[i]) if (flow[i])
			if (!~dis[to[i]] || dis[to[i]] > dis[w] + cost[i]) {
				sur[to[i]] = i;
				dis[to[i]] = dis[w] + cost[i]; 
				cur[to[i]] = min(flow[i], cur[w]);
				if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
			}
	}
	return ~dis[T];
}

inline void MCMF(){
	for (int w=T;SPFA();w=T) {
		F += cur[T];
		while (w != S) {
			flow[sur[w]] -= cur[T];
			flow[sur[w]^1] += cur[T];
			C += cur[T]*cost[sur[w]];
			w = to[sur[w]^1];
		}
	}
}

int main(){
	n = read(); m = read(); S = id(1,1); T = id(n,0);
	for (int i=2;i<n;i++) Add_Edge(id(i,0),id(i,1),1,0);
	for (int i=1,u,v,c;i<=m;i++) 
		u = read(), v = read(), c = read(),
		Add_Edge(id(u,1),id(v,0),1,c);
	MCMF();
	printf("%d %d\n",F,C);
	return 0;
}

【BZOJ 1066】[SCOI2007] 蜥蜴

2016年9月13日2016年9月13日 Qizy 22 Comments

题目传送门：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; 
}

【COGS 746】[网络流24题] 骑士共存

2016年9月13日2016年9月13日 Qizy 21 Comments

题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=746

好吧，我承认我看的是题解……
推荐这家的题解：https://oi.men.ci/cogs-746/

自己来说的话，就是搞一搞二分图？
染色之后，发现有冲突的点都在不同的集合内
于是连边，跑最小割即可

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

const int N = 40000+9;
const int M = N*10;
const int L = 200+9;
const int INF = 10000000;

int head[N],nxt[M],to[M],flow[M],cur[N],dis[N];
int n,m,mat[L][L],vout,S,T; 
int dx[]={0,2,1,-1,-2,-2,-1,1,2};
int dy[]={0,1,2,2,1,-1,-2,-2,-1};
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(){
	freopen("knight.in","r",stdin);
	freopen("knight.out","w",stdout);
	n = read(); m = read(); S = 0; T = N-1; vout = n*n;
	for (int i=1,x,y;i<=m;i++) x = read(), y = read(), mat[x][y] = 1, vout--;
	for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) if (!mat[i][j]) 
		if ((i+j)&1) {
			Add_Edge(S,id(i,j),1); 
			for (int k=1,x,y;k<=8;k++) {
				x = i + dx[k]; y = j + dy[k];
				if (1 <= x && x <= n && 1 <= y && y <= n && !mat[x][y])
					Add_Edge(id(i,j),id(x,y),INF);
			}
		} else Add_Edge(id(i,j),T,1);
	vout -= Dinic();
	printf("%d\n",vout);
	return 0;
}

【BZOJ 4625】[BeiJing2016] 水晶

2016年9月9日2016年9月13日 Qizy 72 Comments

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

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

我们将六边形按照 (x+y+z)%3 == 0/1/2 来分类（染色）
不难发现，会变成这个样子：

之后，我们发现：两种共振一定是三个不同颜色的点产生的
于是把两种共振合起来考虑
因为我们必须任意三个中至少删一个，于是考虑最小割模型
将%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;
}

至于怎样如何很自然地想到这样构图
我也不知道

已经问了YYY，但他还没有回我QAQ

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

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

【BZOJ 4519】[Cqoi2016] 不同的最小割

2016年9月5日2016年9月5日 Qizy 32 Comments

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

分治+最小割
具体来说，假设随便选两个点来做一次最小割x
那么左右点被分成了两个点集，而任意一对存在于不同点集的点的最小割与x的割相等
于是只用考虑每个点集内部的点，接下来的事就是坚持信仰了

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 850+9;
const int M = 8500*2+9;
const int INF = 100000000;

int head[N],nxt[M],to[M],flow[M],cur[N];
int n,m,vout[N*N],cnt,id[N],dis[N],pur,T=1;
queue<int> que;

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

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(int s, int t) {
	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 == pur) 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;
			ret += tmp; f -= tmp; if (!f) return ret;
		}
		return ret;
	}	
}

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

void SIGN(int w) {
	dis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) 
		if (!~dis[to[i]] && flow[i]) SIGN(to[i]);
}

void solve(int l , int r){
	if (l >= r) return ;
	static int tmp[N]; int L=l-1, R=r+1;
	
	for (int i=2;i<=T;i+=2) flow[i] = flow[i^1] = flow[i] + flow[i^1] >> 1;
	vout[++cnt] = Dinic(id[l],id[r]);
	
	memset(dis,-1,sizeof(dis)); SIGN(id[l]); 
	for (int i=l;i<=r;i++) 
		if (~dis[id[i]]) tmp[++L] = id[i];
		else tmp[--R] = id[i];
	for (int i=l;i<=r;i++) id[i] = tmp[i];
	solve(l,L); solve(R,r);
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v,w;i<=m;i++) u = read(), v = read(), w = read(), Add_Edge(u,v,w);
	for (int i=1;i<=n;i++) id[i] = i; solve(1,n); 
	int tot = 0; sort(vout+1,vout+1+cnt); 
	for (int i=1;i<=cnt;i++) if (vout[i] != vout[i-1]) tot++;
	printf("%d\n",tot);
	return 0;
}

【UOJ 78】二分图最大匹配

2016年7月12日2016年7月12日 Qizy 211 Comments

题目传送门：http://uoj.ac/problem/78
离线版题目：http://paste.ubuntu.com/19130171/

今天来搞一搞图论，先来一发二分图。
Dinic此题的时间还是不错的，能踩Dinic的，都只有二分图专门的算法

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 5000000+9;
const int INF = 10000000;

int n1,n2,m,s,t,vout;
int T=1,to[MAXN],nxt[MAXN],head[MAXN];
int dis[MAXN],que[MAXN],fro,bak;
int cap[MAXN],flow[MAXN],cur[MAXN];

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

inline void AddEdge(int a, int b, int CAP){
	to[++T] = b; nxt[T] = head[a]; head[a] = T; cap[T] = CAP;
	to[++T] = a; nxt[T] = head[b]; head[b] = T; cap[T] = 0;
}

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	que[fro=bak=1] = s; dis[s] = 0;
	
	while (bak <= fro) {
		int w = que[bak++];
		for (int i=head[w];i;i=nxt[i])
			if (flow[i] < cap[i] && dis[to[i]] == -1)
				dis[to[i]] = dis[w] + 1, que[++fro] = to[i];
	}
	
	return dis[t] != -1;
}

int MaxFlow(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] < cap[i] && dis[to[i]] == dis[w] + 1){
				int tmp = MaxFlow(to[i], min(f, cap[i]-flow[i]));
				flow[i] += tmp; flow[i^1] -= tmp;
				ret += tmp; if (ret == f) return ret; 
			}
		}
		return ret;
	}
}

inline void Dinic(){
	while (BFS()){
		for (int i=0;i<=t;i++) cur[i] = head[i];
		vout += MaxFlow(s, INF);
	}
}

int main(){
	n1=read(); n2=read(); m=read();
	s = 0; t = n1 + n2 + 1;
	for (int i=1,a,b;i<=m;i++)
		a = read(), b = read(),
		AddEdge(a,n1+b,1);
	for (int i=1;i<=n1;i++) AddEdge(s,i,1);
	for (int i=n1+1;i<=n1+n2;i++) AddEdge(i,t,1);
	Dinic();
	printf("%d\n",vout);
	for (int w=1;w<=n1;w++){
		vout = 0;
		for (int i=head[w];i;i=nxt[i])
			if (flow[i] && to[i] > n1) {
				vout = to[i]-n1; break;
			}
		printf("%d\n",vout);
	}
	return 0;
}

Category: 网络流