【日常小测】仰望星空

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

我们按照极角序来贪心匹配
不难发现这样一定有解

另外Dinic是不能求这种要求字典序最小的解的
似乎只能用最裸的匈牙利

Code

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

const int N = 1009;
const int M = 1000009;
const int INF = 1e9;
const double PI = acos(-1);

int n, R, D, S, T;
int in[N], ot[N], cnt_in, cnt_ot;
int head[N], nxt[M], to[M], mth[N], vis[N];
pair<double, int> arr[N];
struct Point{
	int x, y, ty;
	inline int dis(const Point &P) {
		return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y);
	}
}p[N];

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
} 

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

inline bool DFS(int w) {
	vis[w] = 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) {
			mth[to[i]] = w;
			mth[w] = to[i];
			return 1;
		} 
	}
	return 0;
}

inline int solve() {
	int ret = 0;
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (!mth[i]) {
			memset(vis, 0, sizeof(vis));
			ret += DFS(i);
		}
	}
	return ret;
}

inline void print(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] == mth[w]) {
			vis[w] = vis[to[i]] = 1;
			printf("%d %d\n", w, mth[w]);
			return;
		} else if (!vis[to[i]]){
			print(mth[to[i]]);
		}
	}
}

int main() {
	n = read(); 
	R = read(); R *= R;
	D = read(); D *= D;
	S = 0; T = N - 1;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (p[i].ty = p[i].dis(p[1]) > R) {
			in[++cnt_in] = i;
		} else {
			ot[++cnt_ot] = i;
		}
	}
	for (int ii = 1; ii <= cnt_in; ii++) {
		int i = in[ii], cnt_arr = 0;
		double mx = -PI, mn = PI;
		for (int jj = 1; jj <= cnt_ot; jj++) {
			int j = ot[jj];
			if (p[i].dis(p[j]) <= D) {
				double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
				mx = max(mx, agl);
				mn = min(mn, agl);
				arr[++cnt_arr] = make_pair(agl, j);
			}
		}
		if (mx - mn >= PI) {
			for (int j = 1; j <= cnt_arr; j++) {
				arr[j].first += arr[j].first < 0? PI * 2: 0;
			}
		}
		sort(arr + 1, arr + 1 + cnt_arr);
		for (int j = 1; j <= cnt_arr; j++) {
			AddEdge(i, arr[j].second);
		}
	}
	printf("%d\n", solve() << 1);
	memset(vis, 0, sizeof(vis));
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (mth[i] && !vis[i]) {
			print(i);
		}
	}
	return 0;
}

【BZOJ 1937】[SHOI2004] Mst最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1937
神犇题解:https://blog.sengxian.com/solutions/bzoj-1937

解题报告

我们首先可以得到一个结论:$T$中的边的边权只会减少,其他边的边权只会增加
于是我们将$T$中的边放在左边,其他边放在右边,都作为二分图的点,点权为边权
然后左右两两连边,边权$v_i$为右边点的权值减左边点的权值

此时问题转化为,每一个点设一个$d_i$,满足二分图中任意一条边$i \to j$满足$v_{i \to j} \le d_i + d_j$,求最小化$\sum{d_i}$
这是$KM$算法的关键步骤。于是直接上$KM$算法就可以了

但我不会$KM$算法
←为什么这个频率这个鬼畜啊 QwQ

但不会$KM$算法我们也能做,回忆$KM$算法顶标的作用
最小的顶标和就是最大权匹配的权值和
于是我们用费用流增广这个二分图,直到增广到权值为负就可以了

【CodeChef PARADE】Annual Parade

相关链接

题目传送门:https://www.codechef.com/problems/PARADE
神犇题解:http://blog.csdn.net/jasonvictoryan/article/details/53395098

解题报告

这题先只考虑一个询问的情况

这显然可以使用拆点+二分图最大权匹配去做
具体来说:每个点拆成出度和入度两个点,然后出度放左边,入度放右边
考虑每找到一条增广路,就是在原图中走了一条边
那么不管是连接了两条路径,或是新走到一个点,都会使总费用减少一个$C$
但每走一次增广路,都会花费一些费用$v$
显然我们应该在$v > C$的时候停止增广

现在考虑多个询问
因为是费用流算法,所以单次增广的费用$v_i$是单调不减的
于是我们可以记录每一次增广的$v_i$。对于询问就二分,然后求前缀和就好
当然不想二分,也可以先排个序然后扫一遍,反正总的时间复杂度主要还是卡在费用流那里

【日常小测】Mortal Kombat

题目大意

给定$n(n \le 300)$个外星人,给定$m(m \le 1500)$个地球人,再给定任意地球人与外星人的关系
关系由一个$nm$的0/1矩阵给出,表示第$i$个外星人是否能与第$j$个地球人配对
要求每个外星人至少与一个地球人配对,地球人只能与至多一个外星人匹配
问由哪些关系一定不可能出现在合法的匹配方案中

解题报告

这是一道基础图论题

我们可以先来考虑一个简单的版本:地球人个数与外星人一样
那么我们可以先用二分图匹配跑一个完备匹配出来
此时在匹配中的边一定可以出现在合法的匹配方案中

只考虑不在当前匹配中的边,那么一定是走一条像增广路一样的东西
就是一条匹配边,一条非匹配边交叉着走。最后走一个偶环绕回来
于是我们对于从左边连到右边的边,只保留非匹配边
对于从右到左的边,我们只保留匹配边。这样就可以保证是偶环了
至于能不能走回来,我们发现这就是一个有向图的强连通分量
于是我们再跑一个Tarjan,判断一下就可以了

现在考虑地球人与外星人不等的情况
我们可以把外星人补到与地球人一样多啊!
就是加一些可以与所有地球人匹配的外星人就可以了
当然不加点,大力讨论一波也是可以的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 3009;
const int M = N * N << 1;
const int INF = 1e9;
  
int head[N],nxt[M],to[M],flow[M],low[N],dfs[N];
int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N]; 
stack<int> stk;
  
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 f=0) {
    if (f) {
        to[++E] = v; nxt[E] = head[u]; head[u] = E;
        to[++E] = u, nxt[E] = head[v], head[v] = E;
        flow[E - 1] = f; return E - 1;
    } else to[++E] = v, nxt[E] = head[u], head[u] = E;
}
  
class Network_Flow{
    int dis[N],cur[N]; queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur,head,sizeof(cur));
                ret += DFS(S, INF);
            } return ret;
        }
    private:
        int DFS(int w, int f) {
            if (w == T) return f; int ret = 0;
            for (int &i=cur[w],tmp;i;i=nxt[i]) {
                if (flow[i] && dis[to[i]] == dis[w] + 1) {
                    tmp = DFS(to[i], min(f, flow[i]));
                    flow[i] -= tmp; flow[i^1] += tmp;
                    f -= tmp; ret += tmp;
                    if (!f) return ret;
                }
            } return ret;
        }
        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 (flow[i] && dis[to[i]] > INF) {
                        dis[to[i]] = dis[w] + 1; 
                        que.push(to[i]);
                    }
                }
            } return dis[T] < INF;
        }
}Dinic;
 
void Tarjan(int w) { 
    static int dfs_cnt = 0, scc_cnt = 0; 
    dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
        else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);  
    }
    if (low[w] == dfs[w]) {
        for (scc_cnt++;!stk.empty();stk.pop()) {
            num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
            if (stk.top() == w) {stk.pop(); break;}
        }
    }
}
 
int main() {
    n = read(); m = read(); S = 0; T = N - 1;
    memset(id, -1, sizeof(id));
    for (int i=1;i<=n;i++) {
        scanf("%s",pat+1);
        for (int j=1;j<=m;j++) {
            if (pat[j] == '1') {
                id[i][j] = AddEdge(i, m + j, 1);
            }   
        }
    } 
    for (int i=1;i<=n;i++) AddEdge(S, i, 1);
    for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
    if (Dinic.MaxFlow() != n) {
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) putchar('1');
            puts("");
        }
    } else {
        E = 1; memset(head,0,sizeof(head));
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) 
            if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
        for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
        for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
            if (mth[j] == i) AddEdge(m+j, i); else AddEdge(i, m+j);}
        for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
                else putchar('1');
            } putchar('\n');
        }
    }
    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 2437】[NOI2011] 兔兔与蛋蛋

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2437
神犇题解:http://blog.csdn.net/qpswwww/article/details/45368587

解题报告

我们先将整个棋盘黑白染色,将空格棋子所在方格的颜色分类
在可相互转化的状态之间连边,那么这就是一张二分图了

那么原题的问题转换为:

给定一张二分图,每次沿边移动一次
每个点只能到达一次,最后谁不能动谁就输了
询问每一个点作为起点时是否先手必胜

考虑一个点如果在任意一种最大匹配当中,那么先手每一次走匹配边,则后手必败
换一句话来说,如果一个点一定在最大匹配当中,那么这个点是先手必胜的
再考虑一下,如果一个点不一定在最大匹配当中,那么删掉这个点之后存在最大匹配,那后手走到那个点去就可以了!
再换一句话来说,如果一个点不一定在最大匹配中,那么这个点先手必败

现在我们只需要求出一个点是否在最大匹配中就可以了!
我们可以枚举这个点,将其删掉后跑最大匹配验证,但复杂度是$O(n^4)$的
或者我们可以用今年冬令营的那个一般图匹配的算法来做,时间复杂度是$O(n^3)$的

不过我们可以又一个常数更小的算法

我们可以先求出一个最大匹配,然后假设当点在点$a$
将其删掉后,看$a$的匹配点$b$还能不能匹配即可

吐槽

博弈题居然还能这么玩!
真的是长见识了 _(:з」∠)_
不过代码好难写啊,不想写代码 ┑( ̄Д  ̄)┍

【TopCoder SRM570】Curvy on Rails

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=12432
中文题面:http://www.cnblogs.com/enigma-aw/p/6237246.html
神犇题解:http://metthesoul.blog.163.com/blog/static/23032003620147269343401/

解题报告

首先考虑一个简单的子问题:

给定你一个网格图,其中有一些点有障碍,不能经过
问:能否通过一些回路,使得每一个点恰好经过一次

考虑回路的性质:

  1. 回路中的每一个点的度一定是 $ 2$
  2. 如果每一个点的度都是 $ 2$ ,那么这一定是由一些回路构成的图

这样的话,这个 $ Subcase$ 就可以通过染色后二分图匹配来解决了

现在回到原问题,显然可行解的判断可以用上述算法来解决
现在来考虑 towns with Curvies

在上一个 $ Subcase$ 中使用的二分图匹配,实际上是对 进行匹配
现在考虑将度分类:

  1. 横向的度
  2. 纵向的度

对于 towns with Curvies 来说:如果同类的度匹配,那么就得付出代价
于是考虑将每一个点拆成一个横向的度和纵向的度
然后原图中相邻的格子,只连对应的点(纵向相邻就只连代表纵向的点)
这样的话,如果存在完备匹配,那么一定是一个两个不同类的度匹配

现在再来考虑付出代价的情况:
将二分图匹配改造成费用流,已建的边费用全部为 $ 0$
然后在同一个格子拆开的点之间连一条双向、流量为 $ 1$、费用为 $ 0$ 的边
这样的话,就相当于两个匹配都使用同一类度的时候得付出 $ 1$ 的代价

Code

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

const int L = 30;
const int N = 2000;
const int M = 50000;
const int INF = 1000000000;

int S,T,head[N],nxt[M],to[M],flow[M],cost[M];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};

class Minimum_Cost_Flow{
    int dis[N],sur[N],inq[N];
    queue<int> que;
    public:
        inline pair<int,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 make_pair(ret_cost, ret_flow);
        }
    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;

class CurvyonRails {
	int n,m,cnt,E;
	char pat[L][L];
    public:
    	int getmin(vector<string> field) {
    	    init();
    	    m = field.size();
    	    n = field[0].size();
    	    for (int j=0;j<m;j++) {
				for (int i=0;i<n;i++) {
					pat[i+1][j+1] = field[j][i];
				}
			}
			for (int j=1;j<=m;j++) {
				for (int i=1;i<=n;i++) {
					if (pat[i][j] == 'w') continue;
					else {
						if (++cnt, i + j & 1) {
							Add_Edge(id(i,j,0), T, 1);
							Add_Edge(id(i,j,1), T, 1);
						} else {
							Add_Edge(S, id(i,j,0), 1);
							Add_Edge(S, id(i,j,1), 1);
							for (int k=1,x,y;k<=4;k++) {
								x = i + dx[k];
								y = j + dy[k];
								if (1 <= x && x <= n && 1 <= y && y <= m) {
									if (x == i) Add_Edge(id(i,j,1), id(x,y,1), 1);
									if (y == j) Add_Edge(id(i,j,0), id(x,y,0), 1);
								}
							}
						}
						if (pat[i][j] == '.') {
							Add_Edge(id(i,j,0), id(i,j,1), 1);
							Add_Edge(id(i,j,1), id(i,j,0), 1);
						}
						if (pat[i][j] == 'C') {
							Add_Edge(id(i,j,0), id(i,j,1), 1, 1);
							Add_Edge(id(i,j,1), id(i,j,0), 1, 1);
						}
					}
				}
			}
			pair<int,int> vout = MCMF.MaxFlow();
			if (vout.second < cnt) return -1;
			else return vout.first;
   		}
   	private:
   		inline int id(int x, int y, int t) {
			return ((y-1)*n + (x-1)) * 2 + 1 + t;   
		}
   		inline void init() {
			E = 1; S = cnt = 0; T = N - 1;
			memset(head,0,sizeof(head));   	
		}
   		inline void Add_Edge(int u, int v, int f, int c = 0) {
			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;
		}
};

【TopCoder SRM578】DeerInZooDivOne

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/12/DeerInZooDivOne.html
中文题面:http://paste.ubuntu.com/23693088/
官方题解:https://apps.topcoder.com/wiki/display/tc/SRM+578

解题报告

给定一棵树,让你求两个没有重叠部分的连通块,使得这个连通块同构

这样的话,真的是不会啊!
直接说正解吧!

枚举将两个连通块分开的那条边
定义 \(f(i,j)\) 为以i的子树和j的子树最大同构部分有多大
不难发现答案就是 \(\max (f(i,j))\)

考虑如何求 \(f(i,j)\):
递归处理的话,实际上就是将两个节点的儿子进行配对
于是搞在这里搞二分图带权匹配就可以啦!

Code

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

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

int n,m,S,T;

class Minimum_Cost_Flow{
	int head[N],nxt[M],to[M],flow[M],cost[M];
    int E,vout,dis[N],sur[N],inq[N];
    queue<int> que;
    public:
    	inline void init() {
			E = 1; S = 0; T = N - 1;
			memset(head,0,sizeof(head));
		}
        inline void Add_Edge(int u, int v, int f, int c) {
			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;
		}
        inline int MaxFlow() {
        	vout = 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;
                vout += dis[T] * f;
            }
            return vout;
        }
    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;

class DeerInZooDivOne {
	int ret,t1,t2,q1[N],q2[N],fa[N],f[N][N];
	int E,head[N],to[M],nxt[M],vis[N];
    public:
    	int getmax(vector<int> a, vector<int> b) {
    	    n = a.size(); init();
    	    for (int i=0;i<n;i++) 
				Add_Edge(a[i]+1, b[i]+1);
			for (int i=0;t1=t2=0,i<n;i++) {
				DFS(a[i]+1, b[i]+1, q1, t1);
				DFS(b[i]+1, a[i]+1, q2, t2);
				vis[i*2+1] = vis[(i+1)*2] = 1;
				for (int p1=1;p1<=t1;p1++) {
					Make_Root(q1[p1], q1[p1]);
					for (int p2=1;p2<=t2;p2++) {
						Make_Root(q2[p2], q2[p2]);
						memset(f,-1,sizeof(f));
						ret = max(ret, F(q1[p1], q2[p2]));
					}
				}
				vis[i*2+1] = vis[(i+1)*2] = 0;
			}
			return ret;
		}
   	private:
   		inline void init() {
			E = 0; ret = 1;
			memset(head,0,sizeof(head));		
		}
   		inline void Add_Edge(int u, int v) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E; 
			to[++E] = u; nxt[E] = head[v]; head[v] = E;   
		}
		void DFS(int w, int f, int *arr, int &cnt) {
			arr[++cnt] = w; 
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f) {
					DFS(to[i], w, arr, cnt);
				}
			}
		}
		void Make_Root(int w, int f) {
			fa[w] = f;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[i]) {
					Make_Root(to[i], w);
				} 
			}
		}
		inline int F(int a, int b) {
			if (a > b) swap(a, b);
			if (~f[a][b]) return f[a][b];
			else {
				for (int i=head[a];i;i=nxt[i]) {
					if (to[i] != fa[a] && !vis[i]) {
						for (int j=head[b];j;j=nxt[j]) {
							if (to[j] != fa[b] && !vis[j]) {
								F(to[i], to[j]);	
							}
						}
					}
				}
				MCMF.init();
				for (int i=head[a];i;i=nxt[i]) {
					if (to[i] != fa[a] && !vis[i]) {
						MCMF.Add_Edge(S, to[i], 1, 0);
						for (int j=head[b];j;j=nxt[j]) {
							if (to[j] != fa[b] && !vis[j]) {
								MCMF.Add_Edge(to[i], to[j], 1, -F(to[i], to[j]));	
							}
						}
					}
				}
				for (int i=head[b];i;i=nxt[i]) {
					if (to[i] != fa[b] && !vis[i]) {
						MCMF.Add_Edge(to[i], T, 1, 0);
					}
				}
				f[a][b] = -MCMF.MaxFlow();
				return ++f[a][b];
			}
		}
};

【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 4514】[Sdoi2016] 数字配对

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

他都给你说了是匹配,那肯定是二分图匹配啦!
考虑可以整除,除完之后还是个质数,那么质因数的个数(不是种类)肯定是一奇一偶
于是建成二分图跑一跑MCMF()就行啦!
当然如果你比较刚烈,想跑带权带花树肯定也是可以的啦!

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

const int M = 200+9;
const int N = 100000+9;
const int MX = 100000; 
const int INF = 0x7fffffff;

int pri[N],tot,vis[N],n,A[M],B[M],C[M];
int lft[M],rit[M],tl,tr,sur[M],S,T,inq[M];
int head[M],nxt[N],to[N],flow[N];
LL cost[N],dis[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 Get_Prime_Number(){
	for (int i=2;i<=MX;i++) {
		if (!vis[i]) pri[++tot] = i;
		for (int j=1;j<=tot&&i*pri[j]<=MX;j++) 
			if (i%pri[j]) vis[i*pri[j]] = 1;
			else {vis[i*pri[j]] = 1; break;}
	}
}

inline void Add_Edge(int u, int v, int f, LL 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 divide(int w) {int ret = 0; for (int i=1;i<=tot;i++) while (w%pri[i] == 0) w /= pri[i], ret++; return ret&1;}
inline bool is_prime(int w) {for (int i=1;i<=tot;i++) if (pri[i] >= w) break; else if (w%pri[i] == 0) return false; return true;}

inline bool SPFA(){
	memset(dis,127,sizeof(dis));
	que.push(S); inq[S] = 1; 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 (flow[i] && dis[to[i]] > dis[w] + cost[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] < dis[M-2]; 
}

inline LL MCMF(){
	LL ret = 0, tot_cost = 0; bool tag=1;
	for (int w=T,f;SPFA()&&tag;w=T) {
		for (f=INF;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]); 
		if (dis[T]*f+tot_cost > 0) ret += -tot_cost / dis[T], tag = 0;
		else {
			for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
			ret += f; tot_cost += f*dis[T];
		}
	} return ret;
}

int main(){
	n = read(); Get_Prime_Number(); S = 0; T = M - 1;
	for (int i=1;i<=n;i++) A[i] = read();
	for (int i=1;i<=n;i++) B[i] = read();
	for (int i=1;i<=n;i++) C[i] = read();
	for (int i=1;i<=n;i++) 
		if (divide(A[i])) lft[++tl] = i, Add_Edge(S,i,B[i],0);
		else rit[++tr] = i, Add_Edge(i,T,B[i],0);
	for (int i=1;i<=tl;i++) for (int j=1;j<=tr;j++) {
		int w1 = A[lft[i]], w2 = A[rit[j]]; if (w1 > w2) swap(w1, w2); 
		if (w2 % w1 == 0 && is_prime(w2 / w1)) 
			Add_Edge(lft[i],rit[j],INF,-1LL*C[lft[i]]*C[rit[j]]);
	} printf("%lld\n",MCMF());
	return 0;
}

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

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

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

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

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

题目传送门: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

【UOJ 80】二分图最大权匹配

题目传送门:http://uoj.ac/problem/80
离线版题目:http://paste.ubuntu.com/19138267/

本来想拿MCMF来水一发,结果T到死,不想回忆KMQAQ
管他的,先放在这里不管了,今天的主要任务是带花树!

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 600000;
const int INF = 100000000;

int n1,n2,m,s,t; LL vout;
int T=1,to[MAXN],nxt[MAXN],head[MAXN],cap[MAXN],flow[MAXN],cost[MAXN];
int dis[MAXN],que[MAXN],fro,bak,inq[MAXN],from[MAXN],scr[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, int COST){
	to[++T] = b; from[T] = a; nxt[T] = head[a]; head[a] = T; cap[T] = CAP; cost[T] = COST;
	to[++T] = a; from[T] = b; nxt[T] = head[b]; head[b] = T; cap[T] = 0; cost[T] = -COST;
}

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

inline void MCMF(){
	while (SPFA()){
		int w = t; while (w != s) 
			flow[scr[w]] += 1, flow[scr[w]^1] -= 1, 
			vout += cost[scr[w]], w = from[scr[w]]; 
	}
}

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