【题解】魔术球网络流24题

Prelude

传送到LOJ
又一道不会做的题。。。
这题其实就是最小路径覆盖。

Solution

就是先写一个循环，把当前循环变量\(i\)的出点与满足条件的更小的数\(j\)的入点连边，其余类似于最小路径覆盖。
当最少路径数比\(n\)大时，输出\(i-1\)，输出方案我在这里也用了链表，每循环一次更新一次。。。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 50000;
const int MAXM = 200000;
const int INF = 0x3f3f3f3f;
namespace Dinic {
	struct Edge {
		int u,v,c,f;
		Edge() {}
		Edge(int u,int v,int c,int f):
			u(u), v(v), c(c), f(f) {}
	};
	int n,m,s,t;
	int head[MAXN], nxt[MAXM];
	int dist[MAXN], cur[MAXN];
	Edge edge[MAXN];
	void clear(int _n) {
		n = _n, m = 0;
		for(int i = 0; i < n; ++i)
			head[i] = -1;
	}
	void addedge(int u,int v,int c) {
		edge[m] = Edge(u,v,c,0);
		nxt[m] = head[u];
		head[u] = m++;
		edge[m] = Edge(v,u,0,0);
		nxt[m] = head[v];
		head[v] = m++;
	}
	queue<int> q;
	bool bfs() {
		for(int i = 0; i < n; ++i)
			dist[i] = INF;
		dist[s] = 0;
		q.push(s);
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = head[u]; ~i; i = nxt[i]) {
				Edge &e = edge[i];
				if(e.c > e.f && dist[e.v] == INF) {
					dist[e.v] = dist[u] + 1;
					q.push(e.v);
				}
			}
		}
		return dist[t] != INF;
	}
	int dfs(int u,int res) {
		if(u == t || !res) return res;
		int flow = 0, f;
		for(int &i = cur[u]; ~i; i = nxt[i]) {
			Edge &e = edge[i];
			if(e.c > e.f && dist[e.v] == dist[u] + 1) {
				f = dfs(e.v,min(res,e.c - e.f));
				e.f += f;
				edge[i^1].f -= f;
				flow += f;
				res -= f;
				if(!res) break;
			}
		}
		return flow;
	}
	int maxflow(int _s, int _t) {
		s = _s, t = _t;
		int flow = 0;
		while(bfs()) {
			for(int i = 0; i < n; ++i)
				cur[i] = head[i];
			flow += dfs(s,INF);
		}
		return flow;
	}
}
bool check(int x) {
	int sq = sqrt(x);
	if(sq*sq == x) return 1;
	return 0;
}
struct node {
	int num;
	bool last;
	node *next;
}ans[MAXN];
int main() {
	int n;
	scanf("%d",&n);
	int s = 0, t = 9000;
	Dinic::clear(t + 1);
	int flow = 0;
	for(int i = 1;;++i) {
		for(int j = 1; j < i; ++j)
			if(check(j+i)) Dinic::addedge((j<<1)-1,(i<<1),1);
		Dinic::addedge(s,(i<<1)-1,1);
		Dinic::addedge((i<<1),t,1);
		flow += Dinic::maxflow(s,t);
		if(i-flow > n) {
			printf("%d\n",i-1);
			for(int j = 1; j < i; ++j) {
				if(ans[j].last) continue;
				for(node *u = &ans[j]; u; u = u->next)
					printf("%d ",u->num);
				puts("");
			}
			return 0;
		}
		for(int j = 1; j <= i; ++j) {
			ans[i].last = 0;
			ans[i].next = NULL;
			ans[i].num = i;
		}
		for(int j = 0; j < Dinic::m; ++j) {
			if(Dinic::edge[j].u == s || Dinic::edge[j].u == t || Dinic::edge[j].v == s || Dinic::edge[j].v == t) continue;
			if(Dinic::edge[j].f == 1) {
				ans[(Dinic::edge[j].u + 1) >> 1].next = &ans[(Dinic::edge[j].v + 1) >> 1];
				ans[(Dinic::edge[j].v + 1) >> 1].last = 1;
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cmath>

using namespace std;

const int MAXN = 50000;

const int MAXM = 200000;

const int INF = 0x3f3f3f3f;

namespace Dinic {

struct Edge {

int u,v,c,f;

Edge() {}

Edge(int u,int v,int c,int f):

u(u), v(v), c(c), f(f) {}

};

int n,m,s,t;

int head[MAXN], nxt[MAXM];

int dist[MAXN], cur[MAXN];

Edge edge[MAXN];

void clear(int _n) {

n = _n, m = 0;

for(int i = 0; i < n; ++i)

head[i] = -1;

}

void addedge(int u,int v,int c) {

edge[m] = Edge(u,v,c,0);

nxt[m] = head[u];

head[u] = m++;

edge[m] = Edge(v,u,0,0);

nxt[m] = head[v];

head[v] = m++;

}

queue<int> q;

bool bfs() {

for(int i = 0; i < n; ++i)

dist[i] = INF;

dist[s] = 0;

q.push(s);

while(!q.empty()) {

int u = q.front();

q.pop();

for(int i = head[u]; ~i; i = nxt[i]) {

Edge &e = edge[i];

if(e.c > e.f && dist[e.v] == INF) {

dist[e.v] = dist[u] + 1;

q.push(e.v);

}

return dist[t] != INF;

}

int dfs(int u,int res) {

if(u == t || !res) return res;

int flow = 0, f;

for(int &i = cur[u]; ~i; i = nxt[i]) {

Edge &e = edge[i];

if(e.c > e.f && dist[e.v] == dist[u] + 1) {

f = dfs(e.v,min(res,e.c - e.f));

e.f += f;

edge[i^1].f -= f;

flow += f;

res -= f;

if(!res) break;

}

return flow;

}

int maxflow(int _s, int _t) {

s = _s, t = _t;

int flow = 0;

while(bfs()) {

for(int i = 0; i < n; ++i)

cur[i] = head[i];

flow += dfs(s,INF);

}

return flow;

}

bool check(int x) {

int sq = sqrt(x);

if(sq*sq == x) return 1;

return 0;

}

struct node {

int num;

bool last;

node *next;

}ans[MAXN];

int main() {

int n;

scanf("%d",&n);

int s = 0, t = 9000;

Dinic::clear(t + 1);

int flow = 0;

for(int i = 1;;++i) {

for(int j = 1; j < i; ++j)

if(check(j+i)) Dinic::addedge((j<<1)-1,(i<<1),1);

Dinic::addedge(s,(i<<1)-1,1);

Dinic::addedge((i<<1),t,1);

flow += Dinic::maxflow(s,t);

if(i-flow > n) {

printf("%d\n",i-1);

for(int j = 1; j < i; ++j) {

if(ans[j].last) continue;

for(node *u = &ans[j]; u; u = u->next)

printf("%d ",u->num);

puts("");

}

return 0;

}

for(int j = 1; j <= i; ++j) {

ans[i].last = 0;

ans[i].next = NULL;

ans[i].num = i;

}

for(int j = 0; j < Dinic::m; ++j) {

if(Dinic::edge[j].u == s || Dinic::edge[j].u == t || Dinic::edge[j].v == s || Dinic::edge[j].v == t) continue;

if(Dinic::edge[j].f == 1) {

ans[(Dinic::edge[j].u + 1) >> 1].next = &ans[(Dinic::edge[j].v + 1) >> 1];

ans[(Dinic::edge[j].v + 1) >> 1].last = 1;

}

return 0;

}