BZOJ 3698: XWW的难题（有源汇上下界最大流）

题面

XWW是个影响力很大的人，他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易，需要通过XWW的考核。

XWW给你出了这么一个难题：XWW给你一个N*N的正实数矩阵A，满足XWW性。

称一个N*N的矩阵满足XWW性当且仅当：（1）A[N][N]=0；（2）矩阵中每行的最后一个元素等于该行前N-1个数的和；（3）矩阵中每列的最后一个元素等于该列前N-1个数的和。

现在你要给A中的数进行取整操作（可以是上取整或者下取整），使得最后的A矩阵仍然满足XWW性。同时XWW还要求A中的元素之和尽量大。

题解

首先题目描述有误，A[N][N]不满足(2),(3)

然后上下取整就是上下界，直接上下界最大流。

CODE

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <cmath>

#include <queue>

using namespace std;

template<class T>inline void read(T &x) {

	char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;

	for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');x*=flg;

}

const int MAXN = 220;

const int MAXM = 12000;

const int inf = 1000000000;

int n, out[MAXN], in[MAXN];

int info[MAXN], fir[MAXN], to[MAXM<<1], nxt[MAXM<<1], c[MAXM<<1], cnt = 1;

inline void link(int u, int v, int cc, int rc=0) {

	to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; c[cnt] = cc;

	to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt; c[cnt] = rc;

}

int S, T, dis[MAXN];

queue<int>q; bool vis[MAXN];

bool bfs() {

	memset(dis, -1, sizeof dis);

	dis[S] = 0; q.push(S);

	while(!q.empty()) {

		int u = q.front(); q.pop();

		for(int i = fir[u]; i; i = nxt[i])

			if(c[i] && !~dis[to[i]])

				dis[to[i]] = dis[u] + 1, q.push(to[i]);

	}

	return ~dis[T];

}

int aug(int u, int Max) {

	if(u == T) return Max;

	vis[u] = 1; int flow = 0, delta;

	for(int v, &i = info[u]; i; i = nxt[i])

		if(c[i] && !vis[v=to[i]] && dis[v] == dis[u] + 1 && (delta=aug(v, min(Max-flow, c[i])))) {

			c[i] -= delta, c[i^1] += delta, flow += delta;

			if(flow == Max) break;

		}

	vis[u] = 0; return flow;

}

int Maxflow(int s, int t) {

	int re = 0; S = s, T = t;

	while(bfs()) memcpy(info, fir, sizeof info), re += aug(S, inf);

	return re;

}

inline void add(int u, int v, int ll, int rr) {

	link(u, v, rr-ll);

	in[v] += ll;

	out[u] += ll;

}

int rid[105], cid[105], l[105][105], r[105][105];

int main () {

	read(n); int tot = 0, ans = 0;

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

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

			double x;

			scanf("%lf", &x);

			l[i][j] = floor(x);

			r[i][j] = ceil(x);

		}

	for(int i = 1; i < n; ++i) rid[i] = ++tot;

	for(int i = 1; i < n; ++i) cid[i] = ++tot;

	int s = ++tot, t = ++tot, ss = ++tot, tt = ++tot;

	for(int i = 1; i < n; ++i) add(s, rid[i], l[i][n], r[i][n]);

	for(int j = 1; j < n; ++j) add(cid[j], t, l[n][j], r[n][j]);

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

		for(int j = 1; j < n; ++j) add(rid[i], cid[j], l[i][j], r[i][j]);

	int sum = 0;

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

		if(in[i]>out[i]) link(ss, i, in[i]-out[i]), sum += in[i]-out[i];

		if(in[i]<out[i]) link(i, tt, out[i]-in[i]);

	}

	link(t, s, inf, 0);

	sum -= Maxflow(ss, tt);

	if(sum) puts("No");

	else {

		ans = c[cnt];

		c[cnt] = c[cnt^1] = 0;

		ans += Maxflow(s, t);

		printf("%d\n", ans*3);

	}

}