图论 – Page 5 – Qizy's Database

【BZOJ 1711】[Usaco2007 Open] Dining吃饭

2016年9月18日2016年9月18日 Qizy 20 Comments

题目传送门：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 1391】[Ceoi2008] order

2016年9月18日2016年9月18日 Qizy 81 Comments

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

喜闻乐见大水题

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

const int N = 10000;
const int M = 4000000;
const int INF = 1000000000;

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

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

【Codeforces 715B】Complete The Graph

2016年9月18日2016年9月23日 Qizy 92 Comments

题目传送门：http://codeforces.com/contest/716/problem/D
官方题解：http://codeforces.com/blog/entry/47169

这题很好玩，有两种写法。

1）暴力最短路，复杂度O(nmlogn)
做法就是每一次找最短路，然后改一改

2）神奇二分，复杂度O(mlognlogm)
将可更改的边拉出来，排成一溜
二分一个点k，使1~k的边为1，其余边为INF
终止条件：k时最短路<=l,k-1时最短路>L
于是第k条边就是关键边，只用考虑这条边的长度即可
感觉好神！

考试的时候，我写的是第一种

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

const LL N = 1000+9;
const LL M = 20000+9;
const LL INF = 1e14;

LL head[N],to[M],nxt[M],cost[M],U[M],V[M],dis[N],n,m,L,S,T,sign[M],ty,inq[N],sur[N];
queue<LL> que;

inline LL read(){
	char c=getchar(); LL 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(LL u, LL v, LL d) {
	static LL TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = d;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = d;
}

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

int main(){
	n = read(); m = read(); L = read(); S = read() + 1; T = read() + 1;
	for (LL i=1,tmp;i<=m;i++) {
		U[i] = read()+1, V[i] = read()+1; tmp = read();
		if (!tmp) tmp = -1, sign[i] = 1;
		Add_Edge(U[i],V[i],tmp);
	}
	if (SPFA() < L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = 1;
	if ((ty=SPFA()) > L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = INF;
	LL w = T,len_tmp; while (w != S) {if(sign[sur[w]/2]) cost[sur[w]] = cost[sur[w]^1] = 1; w = to[sur[w]^1];}
	while ((len_tmp=SPFA()) < L) 
		for (w=T;w!=S;w=to[sur[w]^1]) if (sign[sur[w]/2]) {
			cost[sur[w]] += L - len_tmp, cost[sur[w]^1] += L - len_tmp; break;}
	cout<<"YES"<<endl;
	for (LL i=1;i<=m;i++) 
		if (sign[i] && cost[i*2] == -1) printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,L+1);
		else printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,cost[i*2]);
	return 0;
}

【BZOJ 2245】[SDOI2011] 工作安排

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

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

这个题目有一个Trick
对于费用流，如果单位费用是一个单调不减的分段函数
那么可以每一段单独建边

至于这题的代码嘛……
不想写啦！

但如果费用不是单调不减怎么搞？
咨询YYY中…

【BZOJ 1070】[SCOI2007] 修车

2016年9月17日2016年9月23日 Qizy 2 Comments

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

这个题目，最开始想到的肯定是完全按照时间来拆点
这样想起来很直观，然而估计会wa？因为一个车是一个整体，不能中间暂停
于是只能考虑以车为单位来拆点。然后计算贡献。
这题真的是好妙啊！

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

int m,n,s,t,vout;// m means the worker     n means the car
int str[70][20];
struct edge{
	int from,to,cap,cost,flow;
	edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),cost(cost),flow(flow){}
	edge(){}
};
vector<edge> edges;
vector<int> node[700];//1-60 is the car  71-INF is the worker

void addedge(int from,int to,int cap,int flow,int cost){
	edges.push_back( edge(from,to,cap,0,cost) );
	edges.push_back( edge(to,from,0,0,-cost) );
	int asd=edges.size();
	node[from].push_back(asd-2);
	node[to].push_back(asd-1);
}

void init(){
	cin>>m>>n;
	for (int i=1,hc;i<=n;i++){//car
		for (int j=1;j<=m;j++){//worker
		    scanf("%d",&hc);//hc=-hc;
		    for (int k=1,hj;k<=n;k++){
                hj=n+(j-1)*n+k;
				addedge(i,hj,1,0,hc*k);		    	
		    }
		}
	}
	s=0;t=n+n*m+1;
	for (int i=1;i<=n;i++) addedge(0,i,1,0,0);
	for (int i=n+1;i<t;i++) addedge(i,t,1,0,0);
}

int d[1000],a[1000],p[1000],inq[1000];
bool bellman_ford(){
	queue<int> Q;Q.push(s);
	memset(inq,0,sizeof (inq));
	for (int i=1;i<=t;i++) d[i]=0x7ffffeee;
	a[s]=0x7ffffeee;d[s]=0;p[s]=0;inq[s]=1;
	
	while(!Q.empty()) {
		int now=Q.front();Q.pop();inq[now]=0;
		int len=node[now].size();
		for (int i=0;i<len;i++){
			edge& e=edges[node[now][i]];
			if (e.cap>e.flow && d[e.to]>d[now]+e.cost){
				d[e.to]=d[now]+e.cost;
				p[e.to]=node[now][i];
				a[e.to]=min(a[now],e.cap-e.flow);
				if (!inq[e.to]) inq[e.to]=1,Q.push(e.to);
			}
		}
	}
	if (d[t]==0x7ffffeee) return false;
	vout+=d[t]*a[t];
	for (int i=t;i!=s;i=edges[p[i]].from){
		edges[p[i]].flow+=a[t];
		edges[p[i]^1].flow-=a[t];
	}
	return true;
}

int main(){
	init();
	while (bellman_ford()) {}
	printf("%.2f",(double)vout/(double)n);
	return 0;
}

【BZOJ 3275】Number

2016年9月17日2016年10月24日 Qizy 2 Comments

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

这题还是挺有意思的！
首先，肯定一眼能看出来是最小割
然后就是建图了。
1）暴力方法，拆点：http://hzwer.com/2864.html ←这样搞虽然不优雅，但普适性更强？←这样做是错的，详见UPD
2）优雅的方法：写个程序试一试，发现在1000以内的冲突的a,b一定是一奇一偶，于是搞成二分图

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

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

int n,arr[N],head[N],nxt[M],to[M],flow[M],cur[N],dis[N],S,T,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 sqr(x) ((x)*(x))
int GCD(int a, int b) {return b?GCD(b,a%b):a;}
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(); S = 0; T = N - 1;
	for (int i=1;i<=n;i++) arr[i] = read(), vout += arr[i];
	for (int i=1;i<=n;i++) if (arr[i]%2) Add_Edge(S,i,arr[i]); else Add_Edge(i,T,arr[i]);
	for (int i=1;i<=n;i++) if (arr[i]%2) for (int j=1,w=sqr(arr[i])+sqr(arr[j]);j<=n;j++,w=sqr(arr[i])+sqr(arr[j])) 
		if (GCD(arr[i],arr[j])==1 && sqr(int(sqrt(w)+1e-7))== w) Add_Edge(i,j,INF);
	printf("%d\n",vout-Dinic());
	return 0;
}

—– UPD 2016.9.17 —–
给一下证明：
首先同为偶数肯定不成立。
对于同为奇数的情况：
(2a-1)^2+(2b-1)^2=c^2
c^2=4(a(a-1)+b(b-1))+2
不难发现c^2中只有一个2，没有两个2
所以c不可能为整数
得证.

—– UPD 2016.9.18 —–
今天突然想到，如果hzwer那种建模可以在一般图中推广的话
那我们还要带花树干嘛？
所以这题黄学长没证二分图就艹过去了，这完全是运气好啊！
但再仔细想一想，如果是带花树的题，岂不是可以尝试这样去骗分？

【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 1433】[ZJOI2009] 假期的宿舍

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

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

真·水题

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

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

int head[N],nxt[M],to[M],flow[M],TT,in_school[N],live_school[N];
int n,vout,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;
}

inline void Add_Edge(int u, int v, int f) {
	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(){
	int TTT; cin>>TTT; while (TTT--) {
		memset(head,0,sizeof(head));
		memset(in_school,0,sizeof(in_school));
		memset(live_school,0,sizeof(live_school));
		n = read(); vout = 0; TT = 1; S = 0; T = N-1; 
		for (int i=1;i<=n;i++) if (read()) Add_Edge(i+n,T,1), live_school[i] = 1;
		for (int i=1;i<=n;i++) if (!read()) Add_Edge(i,i+n,1), in_school[i] = 1;
		for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) if (read()) Add_Edge(i,j+n,1);
		for (int i=1;i<=n;i++) if (in_school[i] || !live_school[i]) Add_Edge(S,i,1), vout++;
		if(Dinic() == vout)puts("^_^");
        else puts("T_T");
	}
	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;
}

【COGS 396】[网络流24题] 魔术球问题（简化版

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

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

这题，大家都说贪心可以过QAQ
但我总觉得贪心有问题…
贪心那块，不会证明小于a且a+b为完全平方数的数至多存在一个解
于是还是最小路径覆盖比较靠谱吧！

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

const int N = 100000;
const int INF = 10000000;

int head[N],to[N],nxt[N],flow[N],dis[N],cur[N]; 
int n,m,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(x,ty) ((x)*2+ty)
inline int Add_Edge(int u, int v, int f) {
	static int TT = 1;
	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;
	return TT - 1;
}

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

inline int DFS(int w, int f) {
	if (w == T) return f;
	else {
		int ret = 0;
		for (int &i=head[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) 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("balla.in","r",stdin);
	freopen("balla.out","w",stdout);
	n = read(); S = 0; T = 1; 
	for (int i=1,w=0;i<=1600;i++) {
		Add_Edge(S,id(i,0),1); Add_Edge(id(i,1),T,1);
		for (int j=i-1;j;j--) if (i + j == (int)sqrt(i+j)*(int)sqrt(i+j)) Add_Edge(id(i,0),id(j,1),1);
		w += Dinic(); if (i - w > n) cout<<i-1, exit(0);
	}
	return 0;
}

Category: 图论