【Codeforces 802C】Heidi and Library (hard)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/C
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
消圈定理:https://blog.sengxian.com/algorithms/clearcircle

解题报告

被这题强制解锁了两个新姿势qwq

  1. 上下界最小费用流:
    直接按照上下界网络流一样建图,然后正常跑费用流
  2. 带负环的费用流
    应用消圈定理,强行将负环满流

然后考完之后发现脑残了
换一种建图方法就没有负环了_(:з」∠)_

Code

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

const int N = 5000000;
const int M = 200;
const int INF = 1e9;

int n,k,S,T,tot,SS,TT,ans,a[M],np[M],cc[M];
int head[N],nxt[N],to[N],flow[N],cost[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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 AddEdge(int u, int v, int c, int f) {
	static int E = 1;
    to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
}

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N],vis[N]; 
    queue<int> que; 
    public:
        inline void MaxFlow() {
        	while (clearCircle()); 
            for (int ff; ff = INF, SPFA();) {
            	for (int w = TT; w != SS; w = to[sur[w]^1]) {
					ff = min(ff, flow[sur[w]]);
				}
                for (int w = TT; w != SS; w = to[sur[w]^1]) {
					flow[sur[w]] -= ff;
					flow[sur[w]^1] += ff;
				}
				ans += dis[TT] * ff;
            }
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(SS); dis[SS] = 0;
               
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) {
							inq[to[i]] = 1;
							que.push(to[i]);
						}
                    }
                }
            }
            return dis[TT] < INF;
        }
        bool clearCircle() {
        	memset(dis, 0, sizeof(dis));
        	memset(vis, 0, sizeof(vis));
			for (int i = 1; i <= tot; ++i) { 
   	    		if (!vis[i] && DFS(i)) {
					return 1;   
				}
			}
			return 0;
    	}
    	bool DFS(int w) {
    		vis[w] = 1;
    		if (inq[w]) {
    			int cur = w;
    			do {
					flow[sur[cur]]--;
					flow[sur[cur]^1]++;
					ans += cost[sur[cur]];
					cur = to[sur[cur]];
				} while (cur != w);
				return 1;
			} else {
    			inq[w] = 1;
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > dis[w] + cost[i]) {
						dis[to[i]] = dis[w] + cost[i];
						sur[w] = i;
						if (DFS(to[i])) {
							inq[w] = 0;
							return 1;
						}
					}
				}
				inq[w] = 0;
				return 0;
			}
			
		}
}MCMF;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif 
	n = read(); k = read();
	S = tot = n + 4; T = n + 1;
	SS = n + 2; TT = n + 3; 
	AddEdge(T, S, 0, k); 
	AddEdge(S, 1, 0, INF);
	for (int i = 1; i <= n; i++) {
		np[i] = ++tot;
		AddEdge(np[i], i + 1, 0, INF);
		AddEdge(i, np[i], 0, INF);
		AddEdge(i, TT, 0, 1);
		AddEdge(SS, np[i], 0, 1);
		a[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		cc[i] = read();
	}
	for (int i = 1; i <= n; i++) {
		ans += cc[a[i]];
		for (int j = i + 1; j <= n; j++) {
			if (a[i] == a[j]) {
				AddEdge(np[i], j, -cc[a[i]], 1);
				break;
			} 
		}
	}
	MCMF.MaxFlow();
	cout<<ans<<endl; 
	return 0;
}

【LA 5928】[2016-2017 ACM-ICPC CHINA-Final] Mr.Panda and TubeMaster

相关链接

题目传送门:https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=769&page=show_problem&problem=5928

中文题面

Mr. Panda很喜欢玩游戏。最近,他沉迷在一款叫Tube Master的游戏中。
在Tube Master游戏中,玩家可以在$N\times M (N,M \le 30)$的网格中放置管道。每个网格要么为空格子,要么放置下面四种管子中的一种。

当两个相邻(有公共边的格子视为相邻)的格子中间有管道连接(例如下面这幅图),那么玩家将会得到一些分数(具体细节将在输入描述中给出)。

游戏中,有些格子是关键格子。对于每一个关键格子,玩家必须放置这四种管道中的任意一种,不得留空,否则玩家将输掉整局游戏。
玩家放好管道后,这个$N\times M$的网格必须满足以下两个条件,否则玩家将输掉整局游戏。
1. 每个格子要么没有管道,要么这个格子的管道是环形管道的一部分。
2. 每个关键格子必须放置管道。
特别地,如果没有关键格子,那么空网格也是一组合法解。
可以有多个环。

在上面三张图中,灰色格子是关键格子。其中:
左边的图不合法,因为关键格子没有放管道。
中间的图合法。
右边的图不合法,因为管道没有构成环。
Mr. Panda想要打赢这局游戏并且拿到尽可能多的分数。你能帮他计算他最多能拿多少分吗?

解题报告

这是一道非常玄妙的费用流题目

我们先将所有的点黑白染色
然后我们钦定黑点是从横变竖,白点是从竖变横(如果刚好相反的话,我们把这个环给反向就可以了)
之后我们再把每个点拆成入度和出度两个点,入度全部放左边,出度放右边
根据我们的旨意,黑色的入度只能匹配其上下的方格的出度,其出度只能匹配其左右两个方格的入度
我们在连边的时候,注意这个限制。
根据这个题目的启示TopCoder – Curvy on Rails,如果存在完备匹配,这个匹配的意义一定是几个圈

现在唯一的问题就是,有一些点可以不选了
那么我们可以认为他的出度与自己的入度匹配了(自环)
于是对于不必选的点我们连一条自己到自己的边,必选的边不连
之后搞一发费用流就可以了!

Code

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

const int N = 5000;
const int M = 100000;
const int INF = 1e9;

int n,m,S,T,E,head[N],nxt[M],cost[M],flow[M],to[M];
int pos[30][30],cx[30][30],cy[30][30],vis[30][30];

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 AddEdge(int u, int v, int c, int f) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
	return E - 1;
}

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N];
    queue<int> que; 
    public:
        inline int MaxFlow() {
            int ret_cost = 0, ret_flow = 0;
            for (int f=INF,w;SPFA();f=INF) {
                for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
                for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
                ret_cost += dis[T] * f;
                ret_flow += f;
            }
            return ret_flow == n * m? ret_cost: -INF;
        }
    private:
        bool SPFA() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
              
            while (!que.empty()) {
                int w = que.front(); que.pop(); inq[w] = 0;
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
                        dis[to[i]] = dis[w] + cost[i];
                        sur[to[i]] = i;
                        if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
}MCMF;

inline int id(int x, int y, int t) {
	return ((y - 1) * n + x - 1) * 2 + t;
}

int main() {
	for (int TT=read(),t=1;t<=TT;t++) {
		S = 0; T = N - 1; E = 1; memset(head,0,sizeof(head));
		printf("Case #%d: ",t);	m = read(); n = read();
		for (int j=1,v;j<=m;j++) for (int i=1;i<n;i++) cx[i][j] = -read();
		for (int j=1,v;j<m;j++) for (int i=1;i<=n;i++) cy[i][j] = -read();
		for (int e=read(),x,y;e;e--) x=read(), y=read(), vis[y][x] = t;
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				AddEdge(S, id(i,j,1), 0, 1);
				AddEdge(id(i,j,2), T, 0, 1);
				if (vis[i][j] != t) AddEdge(id(i,j,1), id(i,j,2), 0, 1); 
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				if ((i + j) & 1) {
					if (i < n) AddEdge(id(i+1,j,1), id(i,j,2), cx[i][j], 1);
					if (i > 1) AddEdge(id(i-1,j,1), id(i,j,2), cx[i-1][j], 1);
					if (j < m) AddEdge(id(i,j,1), id(i,j+1,2), cy[i][j], 1);
					if (j > 1) AddEdge(id(i,j,1), id(i,j-1,2), cy[i][j-1], 1);
				} 
			}
		}
		int tmp = MCMF.MaxFlow();
		if (tmp == -INF) puts("Impossible");
		else printf("%d\n",-tmp);
	}
	return 0;
}

—————————— UPD 2017.3.22 ——————————
Claris给我讲了一点新的姿势,不需要原来的无源汇带上下界费用流了
只需要一个普通的费用流即可,已经更新
Claris真是太强了 _(:з」∠)_

【BZOJ 3876】[AHOI2014] 支线剧情

相关链接

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

解题报告

就是裸的上下界费用流
但是合并一下边,快了30倍是什么鬼啊

Code

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

const int N = 300 + 9;
const int M = 20000 + 100 << 1;
const int INF = 1e9;

int n,m,vout,T,S,V,cnt[N],head[N],to[M],nxt[M],cost[M],flow[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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, int c) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c; 
}

class Minimum_Cost_Flow{
	int dis[N],sur[N],inq[N];
	queue<int> que;
    public:
    	inline void MaxFlow(bool SPJ=0) {
			for (int f=INF,w;SPFA();f=INF) {
				if (SPJ && dis[T] >= 0) return;
				for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
				for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
				vout += dis[T] * f;
			}
		}
	private:
		bool SPFA() {
			memset(dis,60,sizeof(dis));
			que.push(S); dis[S] = 0;
			
			while (!que.empty()) {
				int w = que.front(); que.pop(); inq[w] = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
						dis[to[i]] = dis[w] + cost[i];
						sur[to[i]] = i;
						if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
					}
				}
			}
			return dis[T] < INF;
		}
}MCMF;

int main() {
	n = read();
	S = 0; T = N - 1; V = N - 2;
	for  (int i=1,k;i<=n;i++) {
		k = read();
		for (int j=1,p,c;j<=k;j++) {
			p = read(); c = read();
			cnt[i]--; cnt[p]++;
			vout += c;
			Add_Edge(i, p, INF, c);
		}
		Add_Edge(i, V, INF, 0);
	}
	Add_Edge(V, 1, INF, 0);
	for (int i=1;i<=n;i++) {
		if (cnt[i] > 0) Add_Edge(S, i, cnt[i], 0);
		else Add_Edge(i, T, -cnt[i], 0);
	}
	MCMF.MaxFlow();
	for (int i=head[S];i;i=nxt[i]) 
		if (flow[i]) return 1;
	S = V; T = 1;
	MCMF.MaxFlow(1);
	printf("%d\n",vout);
	return 0;
}

【算法笔记】上下界网络流问题

无源汇可行流

  1. 问题分析:
    因为只比传统网络流多了下界,所以考虑单独考虑下界的流量

  2. 解决方案:
    于是原来的边拆为上界为min的边并强行满流,和上界为max - min的边。
    但这样可能会出现流量不平衡的状况,及一个点流入的流量不等于流出量。
    于是单独增加源汇点,构造一个完全等价的网络流问题

    至此我们已经将问题转化为传统网络流问题,直接求解即可。
    如何判断是否有可行流的根据也显而易见了:\( Max\_Flow = = \sum {Min\_Flo{w_i}}\)

有源汇可行流

  1. 问题分析:
    有源汇意味着有一对点的流量不守恒,就是这一对点使其于无源汇可行流问题有了差别
    于是我们考虑去掉这个不同点,将其转化为无源汇可行流

  2. 解决方案
    我们注意到,将源汇点连上一条容量INF的边之后,所有的点流量都守恒了
    换一句话来说我们将其转化为了无源汇可行流问题,使用上文所述方法求解即可

有源汇最大流/最小流

  1. 通解通法:
    观察可行流的解决方案,不难发现我们控制我们人为增加的那条边的容量即可控制最大流的容量
    所以我们可以二分最大流/最小流,之后进行可行流判断,再之后根据结果进行调整即可

  2. 最小流的高效算法:
    先不连t-s的那条容量为INF的边,先跑一次附加源汇的最大流
    连t-s的那条边,在残量网络上继续跑附加源汇最大流
    此时t-s那条边的流量是最小的,使用上文所述方法判断其是否为可行流即可

  3. 最大流的高效算法
    连t-s的那条容量为INF的边,跑一次附加源汇最大流
    连t-s的那条边,在残量网络上继续跑s-t的最大流
    此时t-s那条边的流量是最小的,使用上文所述方法判断其是否为可行流即可