Record - Dec. all, 2020

首页

关于

笔记

文章

友链

Record - Dec. all, 2020 - Training REC

cirnovsky / Dec 05, 2020

∆ CF24D Broken robot - AC

设 $f_{i,j}$ 为从 $(i,j)$ 走到最后一排的期望步数，则有方程

f_{i,j}=\frac{1}{4}(f_{i,j-1}+f_{i,j+1}+f_{i+1,j}+f_{i,j})

直接高斯消元 $\Theta(nm^{3})$ 死有余辜。

仔细考虑一下，因为一个 $f_{i,j}$ 在同行的依赖项最多三个，所以一行中一共只有 $3$ 个未知数。

那么复杂度就成了 $\Theta(nm)$ 。

对了边界：

f_{i,1}=\frac{1}{3}(f_{i,1}+f_{i,2}+f_{i+1,1}) \\ f_{i,m}=\frac{1}{3}(f_{i,m}+f_{i,m-1}+f_{i+1,m})

特判 $m=1$ 。

#include <cstdio>

namespace mySpace {
const int MAXN = 1e3 + 5;

int n, m, s, t;
double mat[MAXN][MAXN], sol[MAXN][MAXN];

void Eradicate () {
	for ( int i = 1; i < m; ++ i ) {
		double tmp = mat[i][i]; mat[i][i] = 1;
		mat[i][i + 1] /= tmp, mat[i][m + 1] /= tmp;
		tmp = mat[i + 1][i];
		mat[i + 1][i] = 0, mat[i + 1][i + 1] -= tmp * mat[i][i + 1];
		mat[i + 1][m + 1] -= tmp * mat[i][m + 1];
	}
	mat[m][m + 1] /= mat[m][m], mat[m][m] = 1;
	for ( int i = m - 1; i; -- i )	mat[i][m + 1] -= mat[i + 1][m + 1] * mat[i][i + 1];
}

void main () {
	scanf ( "%d%d%d%d", &n, &m, &s, &t );
	for ( int i = n - 1; i >= s; -- i ) {
		if ( m == 1 )	mat[1][1] = -1.0 / 2, mat[1][m + 1] = -sol[i + 1][1] / 2 - 1;
		else {
			mat[1][1] = -2.0 / 3, mat[1][2] = 1.0 / 3, mat[1][m + 1] = -sol[i + 1][1] / 3 - 1;
			for ( int j = 2; j < m; ++ j ) {
				mat[j][j] = -3.0 / 4;
				mat[j][j - 1] = mat[j][j + 1] = 1.0 / 4;
				mat[j][m + 1] = -sol[i + 1][j] / 4.0 - 1;
			}
			mat[m][m] = -2.0 / 3, mat[m][m - 1] = 1.0 / 3, mat[m][m + 1] = -sol[i + 1][m] / 3 - 1;
		}
		Eradicate ();
		for ( int j = 1; j <= m; ++ j )	sol[i][j] = mat[j][m + 1];
	}
	printf ( "%.4lf\n", sol[s][t] );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ P3211 [HNOI2011]XOR和路径 - AC

异或的期望 $\neq$ 期望的异或（悲

按位考虑，设 $f_{u,0/1}$ 为 $1\rightarrow u$ 异或值第 $i$ 位 $0/1$ 的概率。

等一下非 $0$ 即 $1$ 。

之前作废）设 $f_{u}$ 为到 $u\rightarrow n$ 时，异或值的第 $i$ 位为 $1$ 的概率（后转期望），这个 $i$ 不需要带进状态里。

则有转移：

f_{u}=\begin{cases} \displaystyle \sum_{(u,v)\in E}\frac{1}{d_{u}}f_{v},\text{weight}(u,v)_{i}=1 \\ \displaystyle \sum_{(u,v)\in E}\frac{1}{d_{u}}(1-f_{v}),\text{weight}(u,v)_{i}=0 \\ \end{cases}

最后的答案就是对所有位求和。

#include <cstdio>
#include <cstring>

namespace mySpace {
const double EPS = 1e-8;
const int MAXL = 31;
const int MAXN = 100 + 5, MAXM = 10000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T ABS ( const _T x ) { return x < 0 ? -x : x; }
template<typename _T> void swapp ( _T &x, _T &y ) { _T w = x; x = y; y = w; }

struct GraphSet {
	int to, nx, wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {};
	GraphSet ( const int a, const int b, const int c ) : to ( a ), nx ( b ), wt ( c ) {};
} as[MAXM * 2];

int n, m, bgn[MAXN], cntot, d[MAXN];
double mat[MAXM][MAXN], sol[MAXN];

void makeEdge ( const int u, const int v, const int w ) { as[++ cntot] = GraphSet ( v, bgn[u], w ), bgn[u] = cntot; }

void Eradicate () {
	for ( int i = 1; i <= n; ++ i ) {
		int p = i;
		for ( int j = i + 1; j <= n; ++ j ) {
			if ( ABS ( mat[p][i] ) < ABS ( mat[j][i] ) )	p = i;
		}
		for ( int j = i + 1; j <= n + 1; ++ j )	swapp ( mat[p][j], mat[i][j] );
		if ( ABS ( mat[i][i] ) < EPS )	continue;
		for ( int j = 1; j <= n; ++ j ) {
			if ( i == j )	continue;
			double d = mat[j][i] / mat[i][i];
			for ( int k = 1; k <= n + 1; ++ k )	mat[j][k] -= mat[i][k] * d;
		}
	}
	for ( int i = 1; i <= n; ++ i )	mat[i][n + 1] /= mat[i][i], sol[i] = mat[i][n + 1];
}

void main () {
	n = rint (), m = rint ();
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint (), w = rint ();
		if ( u == v )	d[u] ++, makeEdge ( u, v, w );
		else {
			makeEdge ( u, v, w ), makeEdge ( v, u, w );
			d[u] ++, d[v] ++;
		}
	}
	double ans = 0;
	for ( int k = 0; k <= MAXL; ++ k ) {
		memset ( mat, 0, sizeof ( mat ) ), mat[n][n] = 1;
		for ( int _ = 1; _ < n; ++ _ ) {
			int u = _; mat[u][u] = d[u];
			for ( int i = bgn[u]; i; i = as[i].nx ) {
				int v = as[i].to, w = as[i].wt;
				if ( ( w >> k ) & 1 )	mat[u][v] ++, mat[u][n + 1] ++;
				else	mat[u][v] --;
			}
		}
		Eradicate (), ans += sol[1] * ( 1ll << k );
	}
	printf ( "%.3lf\n", ans );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ NOIP2020 A 排水系统 - AC

找出所有的起点 DFS 即可，可以手动实现一个分数类。

/* Beware of your __INT128 */

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

namespace MySpace {
typedef long long LL;

const __int128 MAXN = 1e5 + 5, MAXS = 10 + 5, MAXE = 1e5 + 5;

__int128 rint () {
	__int128 x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = ( c == '-' ? -1 : f );
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 + '0' );
}

__int128 calcGCD ( const __int128 a, const __int128 b ) ;
__int128 calcLCM ( const __int128 a, const __int128 b ) ;

struct GraphSet {
	__int128 to, nx;
	GraphSet ( __int128 T = 0, __int128 N = 0 ) { to = T, nx = N; }
} as[MAXN * 5 * 4];

struct Frac {
	__int128 one, ano;
	Frac ( __int128 O = 0, __int128 A = 0 ) { one = O, ano = A; }
} nds[MAXN];

__int128 n, stn, edn, bgn[MAXN], cnte, ind[MAXN], outd[MAXN], sts[MAXN], eds[MAXN], stnd, ednd, vis[MAXN];

void makeEdge ( const __int128 u, const __int128 v ) { as[++ cnte] = GraphSet ( v, bgn[u] ), bgn[u] = cnte; }
__int128 calcGCD ( const __int128 a, const __int128 b ) { return ! b ? a : calcGCD ( b, a % b ); }
__int128 calcLCM ( const __int128 a, const __int128 b ) { return ( ! a || ! b ) ? 0 : ( __int128 )a / calcGCD ( a, b ) * b; }
void getSimp ( Frac& fr ) { __int128 ret = calcGCD ( fr.one, fr.ano ); if ( ! ret )	fr = Frac (); else fr.one /= ret, fr.ano /= ret; }

void dfs ( const __int128 u ) {
	for ( __int128 i = bgn[u]; i; i = as[i].nx ) {
		__int128 v = as[i].to;
		Frac ad = Frac ( nds[u].one, nds[u].ano * outd[u] );
		getSimp ( ad );
		__int128 ret = calcLCM ( ad.ano, nds[v].ano );
		if ( ! ret )	nds[v] = ad, dfs ( v );
		else {
			__int128 ads = ret / ad.ano, us = ret / nds[v].ano;
			ad.one *= ads, ad.ano *= ads;
			nds[v].one *= us, nds[v].ano *= us;
			nds[v].one += ad.one;
			getSimp ( nds[v] );
			dfs ( v );
		}
	}
	if ( bgn[u] )	nds[u] = Frac ();
}

void Main () {
	n = rint (), stn = rint ();
	for ( __int128 i = 1; i <= n; ++ i ) {
		__int128 eg = rint ();
		for ( __int128 j = 1; j <= eg; ++ j ) {
			__int128 to = rint ();
			makeEdge ( i, to );
			ind[to] ++, outd[i] ++;
		}
	}
	for ( __int128 i = 1; i <= n; ++ i ) {
		if ( ! ind[i] )	sts[++ stnd] = i;
		if ( ! outd[i] )	eds[++ ednd] = i;
	}
	for ( __int128 i = 1; i <= stnd; ++ i )	nds[sts[i]].one = nds[sts[i]].ano = 1;
	sort ( eds + 1, eds + 1 + ednd );
	for ( __int128 i = 1; i <= stnd; ++ i )	dfs ( i );
	for ( __int128 i = 1; i <= ednd; ++ i )	wint ( nds[eds[i]].one ), putchar ( ' ' ), wint ( nds[eds[i]].ano ), putchar ( '\n' );
}
}

int main () {
//	freopen ( "water.in", "r", stdin );
//	freopen ( "water.out", "w", stdout );
	MySpace :: Main ();
	return 0;
}

∆ NOIP2020 B 字符串匹配 - AC

这里是 $\Theta(Tn\ln n+26Tn)$ ，我 yy 出来的一个 $\Theta(n\ln n+Tn)$ 的做法由于太过繁杂不想想了。

首先枚举 $AB$ 即循环节，然后挨个往后面跳记个数就好了。

#include <cstdio>
#include <cstring>

namespace mySpace {
typedef long long LL;

const int KEY = 1331;
const int MAXN = ( 1 << 20 ) + 5;

int mul ( const LL a, const LL b, const int p ) { return a * b % p; }
int add ( const int a, const int b, const int p ) { return ( a + b ) < p ? ( a + b ) : ( a + b - p ); }
int sub ( const int a, const int b, const int p ) { return ( a - b ) < 0 ? ( a - b + p ) : ( a - b ); }
struct Value {
	static const int onemod = 19260817, anomod = 998244353;
	int p, q;
	Value () : p ( 0 ), q ( 0 ) {}
	Value ( const int x ) : p ( x ), q ( x ) {}
	Value ( const int a, const int b ) : p ( a ), q ( b ) {}
	Value operator * ( const Value &other ) const { return Value ( mul ( p, other.p, onemod ), mul ( q, other.q, anomod ) ); }
	Value operator + ( const Value &other ) const { return Value ( add ( p, other.p, onemod ), add ( q, other.q, anomod ) ); }
	Value operator - ( const Value &other ) const { return Value ( sub ( p, other.p, onemod ), sub ( q, other.q, anomod ) ); }
	bool operator == ( const Value &other ) const { return p == other.p && q == other.q; }
	bool operator != ( const Value &other ) const { return ! ( Value ( p, q ) == other ); }
} pwr[MAXN], has[MAXN];

int n, mps[MAXN], buc[MAXN][26], suf[MAXN];
char str[MAXN];

void initial () {
	scanf ( "%s", str + 1 ), n = strlen ( str + 1 );
	for ( int i = 1; i <= n; ++ i )	mps[i] = str[i] - 'a';
	bool tmp[26] = {}; int cur = 0;
	for ( int i = 1; i <= n; ++ i ) {
		has[i] = has[i - 1] * KEY + mps[i];
		memcpy ( buc[i], buc[i - 1], sizeof ( int ) * 26 );
		tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1;
		for ( int j = cur; j < 26; ++ j )	buc[i][j] ++;
	}
	memset ( tmp, 0, sizeof ( tmp ) ), cur = 0;
	for ( int i = n; i; -- i )	tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1, suf[i] = cur;
}

Value calcHS ( const int l, const int r ) { return has[r] - has[l - 1] * pwr[r - l + 1]; }
void solve () {
	initial (); LL ans = 0;
	for ( int len = 2; len < n; ++ len ) {
		Value tmp = calcHS ( 1, len );
		for ( int nxt = len; nxt < n; nxt += len ) {
			if ( calcHS ( nxt - len + 1, nxt ) != tmp )	break;
			ans += buc[len - 1][suf[nxt + 1]];
		}
	}
	printf ( "%lld\n", ans );
}

void main () {
	pwr[0] = 1;
	for ( int i = 1; i <= MAXN - 5; ++ i )	pwr[i] = pwr[i - 1] * KEY;
	int TC; scanf ( "%d", &TC );
	while ( TC -- > 0 )	solve ();
}
}

int main () {
//	freopen ( "string.in", "r", stdin );
//	freopen ( "string.out", "w", stdout );
	mySpace :: main ();
	return 0;
}

∆ NOIP2020 C 移球游戏 - AC

首先肯定这是 $n$ 个栈。先看 $n=2$ 的部分分。

这种情况只有黑白两色。

设 $1$ 柱有 $b$ （总共）个黑棋，有 $w$ 个白棋，把 $2$ 柱上 $b$ 个棋子放到 $3$ 柱上，然后重复：

把 $1$ 柱顶部所有黑棋放到 $2$ 柱上。
然后把 $1$ 柱上所有白棋放到 $3$ 柱。

直到 $1$ 柱为空。

然后把 $3$ 柱上面本属于 $1$ 柱的白棋放回去，又把 $2$ 柱上面的 $b$ 个黑棋放到 $1$ 柱去。

于是乎现在 $1$ 柱的情况大概是这样的：

假设原本是这样的：

\begin{aligned} &\texttt{W W B W W B W W B B B} \\ &\texttt{W B W B B B W B W B W} \end{aligned}

那么现在移完后是这样：

\begin{aligned} &\texttt{W W W W W W B B B B B} \\ &\texttt{W B W B B B} \\ &\texttt{W B W B W} \end{aligned}

然后我们把此时 $2$ 柱上的棋子全部放到 $3$ 柱上去，然后就划分一下就完了。

后面的事情就简单了，当 $n>2$ 的时候打个分治，一半一半划分染色，然后按着按着整理。

（代码和 CQ 队长 jiangly 对拍过，不过莫名奇妙就变成了基因比照，于是代码就基本变成了 jiangly 的）

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

namespace mySpace {
const int MAXN = 50 + 5, MAXM = 400 + 5, MAXK = 820000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

struct Stack {
private:
	int stk[MAXM], _top;
public:
	Stack () { memset ( stk, 0, sizeof ( stk ) ), _top = 0; }
	void push ( const int val ) { stk[_top ++] = val; }
	void pop () { if ( _top )	_top --; }
	int at ( const int pos ) { return stk[pos]; }
	int top () { return stk[_top - 1]; }
	int size () { return _top; }
	bool empty () { return _top < 0; }
	void debug ( char c = ' ' ) {
		putchar ( '[' );
		for ( int i = 0; i < _top; ++ i )	printf ( "%d ", stk[i] );
		printf ( "]%c", c ) ;
	}
} clr[MAXN];

struct Answer {
	int one, ano;
	Answer ( int O = 0, int A = 0 ) { one = O, ano = A; }
} ans[MAXK];

int n, m, cnt;

void trans ( const int one, const int ano ) {
	clr[ano].push ( clr[one].top () );
	clr[one].pop ();
	ans[cnt ++] = Answer ( one, ano );
}

void solve ( const int l, const int r, const vector<int>& col ) {
	if ( r - l == 1 )	return;
	int mid = ( l + r ) >> 1;
	int lst = col[0];
	vector<int> onevec, anovec;
	for ( int i = 1; i < r - l; ++ i ) {
		int one = lst, ano = col[i], cnt = 0;
		for ( int j = 0; j < m; ++ j ) {
			if ( clr[one].at ( j ) < mid )	++ cnt;
		}
		for ( int j = 0; j < cnt; ++ j )	trans ( ano, n );
		for ( int j = m - 1; ~ j; -- j ) {
			if ( clr[one].at ( j ) < mid )	trans ( one, ano );
			else	trans ( one, n );
		}
		for ( int j = 0; j < m - cnt; ++ j )	trans ( n, one );
		for ( int j = 0; j < cnt; ++ j )	trans ( ano, one );
		for ( int j = 0; j < m - cnt; ++ j )	trans ( ano, n );
		for ( int j = 0; j < cnt; ++ j )	trans ( one, ano );
		for ( int j = m - 1; ~ j; -- j ) {
			if ( clr[ano].size () < m && ( clr[n].at ( j ) < mid || clr[one].size () == m ) )	trans ( n, ano );
			else	trans ( n, one );
		}
		bool was = 0;
		for ( int j = 0; j < m; ++ j ) {
			if ( clr[ano].at ( j ) >= mid )	was = 1;
		}
		if ( was )	anovec.push_back ( one ), lst = ano;
		else	onevec.push_back ( ano ), lst = one;
	}
	if ( clr[lst].at ( 0 ) < mid )	onevec.push_back ( lst );
	else	anovec.push_back ( lst );
	solve ( l, mid, onevec ), solve ( mid, r, anovec );
}

void main () {
	n = rint (), m = rint ();
	for ( int i = 0; i < n; ++ i ) {
		for ( int j = 0; j < m; ++ j )	clr[i].push ( rint () - 1 );
	}
	vector<int> col;
	for ( int i = 0; i < n; ++ i )	col.push_back ( i );
	solve ( 0, n, col );
	wint ( cnt ), putchar ( '\n' );
	for ( int i = 0; i < cnt; ++ i ) {
		wint ( ans[i].one + 1 ), putchar ( ' ' );
		wint ( ans[i].ano + 1 ), putchar ( '\n' );
	}
}
}

int main () {
//	freopen ( "ball.in", "r", stdin );
//	freopen ( "ball.out", "w", stdout );
	mySpace :: main ();
	return 0;
}

∆ HDU6333 Harvest of Apples - AC

令

F(n,k)=\sum_{i=0}^{m}\binom{n}{i}

然后由

\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

可以得到

F(n,k)=F(n,k-1)+\binom{n}{k}=2F(n-1,k)-\binom{n-1}{k}

然后把 $n,m$ 当成一个区间询问，就可以用上面两个式子来莫队了。

#include <cstdio>
#include <algorithm>

using namespace std;

namespace CaptainMo {
#define mod ( 1000000007 )

typedef long long LL;

const int MAXN = 1e5 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

struct Quest {
	int l, r, whr, ID;
	Quest () : l ( 0 ), r ( 0 ), whr ( 0 ), ID ( 0 ) {}
	Quest ( const int a, const int b, const int c, const int d ) : l ( a ), r ( b ), whr ( c ), ID ( d ) {}
	bool operator < ( const Quest& other ) const {
		if ( whr != other.whr )	return l < other.l;
		else if ( whr & 1 )	return r < other.r;
		else	return r > other.r;
	}
} as[MAXN];

int m, eac, fac[MAXN], ifac[MAXN], ans[MAXN];
LL cur = 1;

int add ( const int a, const int b ) { return ( a + b ) > mod ? a + b - mod : a + b; }
int sub ( const int a, const int b ) { return ( a - b ) < 0 ? a - b + mod : a - b; }
int mul ( const int a, const int b ) { return ( LL )a * b % mod; }
int binom ( const int n, const int k ) { return n < k ? 0 : ( LL )mul ( fac[n], mul ( ifac[n - k], ifac[k] ) ); }
void add1 ( const int n, const int k ) { cur = sub ( mul ( cur, 2 ), binom ( n - 1, k ) ); }
void add2 ( const int n, const int k ) { cur = add ( cur, binom ( n, k ) ); }
void sub1 ( const int n, const int k ) { cur = mul ( add ( cur, binom ( n - 1, k ) ), ifac[2] ); }
void sub2 ( const int n, const int k ) { cur = sub ( cur, binom ( n, k ) ); }

int qkpow ( int base, int indx ) {
	int res = 1;
	for ( ; indx; indx >>= 1 ) {
		if ( indx & 1 )	res = mul ( res, base );
		base = mul ( base, base );
	}
	return res;
}

void initial ( const int n ) {
	fac[0] = 1, eac = 320;
	for ( int i = 1; i <= n; ++ i )	fac[i] = mul ( fac[i - 1], i );
	for ( int i = 0; i <= n; ++ i )	ifac[i] = qkpow ( fac[i], mod - 2 );
}

void contribute () {
	int nowl = 1, nowr = 0;
	for ( int i = 1; i <= m; ++ i ) {
		for ( ; nowl < as[i].l; add1 ( ++ nowl, nowr ) ) ;
		for ( ; nowr < as[i].r; add2 ( nowl, ++ nowr ) ) ;
		for ( ; nowl > as[i].l; sub1 ( nowl --, nowr ) ) ;
		for ( ; nowr > as[i].r; sub2 ( nowl, nowr -- ) ) ;
		ans[as[i].ID] = cur;
	}
}

void main (){
	m = rint (), initial ( MAXN - 5 );
	for ( int i = 1; i <= m; ++ i ) {
		int l = rint (), r = rint ();
		as[i] = Quest ( l, r, l / eac, i );
	}
	sort ( as + 1, as + 1 + m );
	contribute ();
	for ( int i = 1; i <= m; ++ i )	wint ( ans[i] ), putchar ( '\n' );
}
}

int main () {
	CaptainMo :: main ();
	return 0;
}

∆ UVA10892 LCM Cardinality - AC

水计数。

/* Clearink */

#include <cstdio>

namespace mySpace {
typedef long long LL;

LL rint () {
	LL x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

LL n;

LL calcGCD ( const LL a, const LL b ) { return ! b ? a : calcGCD ( b, a % b ); }
LL calcLCM ( const LL a, const LL b ) { return a / calcGCD ( a, b ) * b; }

void main () {
	for ( ; ; ) {
		n = rint ();
		if ( ! n )	break;
		LL bkp = n;
		LL ans = 1;
		for ( LL i = 2; i * i <= bkp; i += 2 ) {
			if ( ! ( bkp % i ) ) {
				int cur = 0;
				for ( ; ! ( bkp % i ); ++ cur )	bkp /= i;
				ans = ( LL )ans * ( cur << 1 | 1 );
			}
			if ( i == 2 )	-- i;
		}
		if ( bkp > 1 )	ans += ans << 1;
		wint ( n ), putchar ( ' ' );
		wint ( ( ans >> 1 ) + 1 ), putchar ( '\n' );
	}
}
}

int main () {
//	freopen ( "lcm.in", "r", stdin );
//	freopen ( "lcm.out", "w", stdout );
	mySpace :: main ();
	return 0;
}

∆ LC874 模拟行走机器人 - AC (LeetCode)

水题。

/* Clearink */

#include <set>
#include <cstdio>

using namespace std;

namespace mySpace {
const int MAXN = 1e4 + 5, MAXZ = 1e3 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T cud ( const _T x ) { return x * x; } // warning: LONG LONG ?
template<typename _T> _T dis ( const _T x, const _T y ) { return cud ( x ) + cud ( y ); }
template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }

struct Point {
	int x, y;
	Point () : x ( 0 ), y ( 0 ) {}
	Point ( const int a, const int b ) : x ( a ), y ( b ) {}
	bool operator < ( const Point& other ) const { return x == other.x ? y < other.y : x < other.x; }
} as[MAXN];

int wax[4], way[4];
int n, m, cd[MAXN];
bool vis[MAXZ][MAXZ];

void initial () {
	n = rint (), m = rint ();
	for ( int i = 1; i <= n; ++ i )	cd[i] = rint ();
	for ( int i = 1; i <= m; ++ i ) {
		int x = rint (), y = rint ();
		as[i] = Point ( x + 500, y + 500 );
	}
	wax[0] = 1, wax[1] = 0, wax[2] = -1, wax[3] = 0;
	way[0] = 0, way[1] = 1, way[2] = 0, way[3] = -1;
}

void main () {
	initial ();
	for ( int i = 1; i <= m; ++ i )	vis[as[i].y][as[i].x] = 1;
	int nowx = 500, nowy = 500, nowd = 0, ans = 0;
	// 0 up | 1 left | 2 down | 3 right
	for ( int _ = 1; _ <= n; ++ _ ) {
		int ccd = cd[_];
		if ( ccd == -1 )	nowd = ( nowd + 5 ) % 4;
		else if ( ccd == -2 )	nowd = ( nowd + 3 ) % 4;
		else {
			for ( int i = 0; i < ccd; ++ i ) {
				int nxtx = nowx + wax[nowd];
				int nxty = nowy + way[nowd];
				if ( nxtx < 0 || nxtx > 1000 || nxty < 0 || nxty > 1000 )	break;
				if ( vis[nxtx][nxty] )	break;
				nowx = nxtx, nowy = nxty;
			}
			ans = MAX ( ans, dis ( nowx - 500, nowy - 500 ) );
		}
	}
	wint ( ans ), putchar ( '\n' );
}
}

int main () {
//	freopen ( "robot.in", "r", stdin );
//	freopen ( "robot.out", "w", stdout );
	mySpace :: main ();
	return 0;
}

∆ LOC3551 教主的魔法 - AC

分块，板题，完了。

/* Clearink */

#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

namespace mySpace {
const long long MAXN = 1000000 + 5, MAXM = 1e4 + 5;

inline long long rint () {
	long long x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
inline void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> inline _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

vector<long long> ink[MAXM];
long long n, m, a[MAXN], eac, cud, pos[MAXN], lps[MAXM], rps[MAXM], adt[MAXN];

inline void redoit ( const long long p ) {
	ink[p].clear ();
	for ( long long i = lps[p]; i <= rps[p]; ++ i )	ink[p].push_back ( a[i] );
	sort ( ink[p].begin (), ink[p].end () );
}

inline void modify ( const long long l, const long long r, const long long w ) {
	for ( long long i = l; i <= MIN ( r, rps[pos[l]] ); ++ i )	a[i] += w;
	redoit ( pos[l] );
	if ( pos[l] != pos[r] ) {
		for ( long long i = lps[pos[r]]; i <= r; ++ i )	a[i] += w;
		redoit ( pos[r] );
	}
	for ( long long i = pos[l] + 1; i < pos[r]; ++ i )	adt[i] += w;
}

inline long long trans ( const long long x, const long long c ) { return x >= c; }
inline long long calcID ( const long long p, const long long x ) { return lower_bound ( ink[p].begin (), ink[p].end (), x ) - ink[p].begin (); }
inline long long query ( const long long l, const long long r, const long long c ) {
	long long res = 0;
	for ( long long i = l; i <= MIN ( r, rps[pos[l]] ); ++ i )	res += trans ( a[i] + adt[pos[l]], c );
	if ( pos[l] != pos[r] ) {
		for ( long long i = lps[pos[r]]; i <= r; ++ i )	res += trans ( a[i] + adt[pos[r]], c );
	}
//	printf ( "(%d %d %d %d %d)\n", l, rps[pos[l]], lps[pos[r]], r, res );
	for ( long long i = pos[l] + 1; i < pos[r]; ++ i )	res += ( long long )ink[i].size () - calcID ( i, c - adt[i] );
	return res;
}

void main () {
	n = rint (), m = rint ();
	eac = sqrt ( n ), cud = n / eac; if ( eac * eac != n )	cud ++; // warning: remember to fuck it !
//	eac = 1001, cud = n / eac + 1;
	for ( long long i = 1; i <= n; ++ i )	a[i] = rint ();
	for ( long long i = 1; i <= cud; ++ i ) {
		lps[i] = rps[i - 1] + 1;
		rps[i] = rps[i - 1] + eac;
		if ( i == cud )	rps[i] = n;
		for ( long long j = lps[i]; j <= rps[i]; ++ j )	pos[j] = i, ink[i].push_back ( a[j] );
	}
//	for ( long long i = 1; i <= cud; ++ i ) {
//		printf ( "[" );
//		for ( long long j = lps[i]; j < rps[i]; ++ j )	printf ( "%d ", a[j] );
//		printf ( "%d] ", a[rps[i]] );
//	}
//	puts ( "" );
	for ( long long i = 1; i <= cud; ++ i )	sort ( ink[i].begin (), ink[i].end () );
	for ( ; m; m -- ) {
		char opt[5]; scanf ( "%s", opt );
		long long l = rint (), r = rint (), w = rint ();
		if ( opt[0] == 'M' )	modify ( l, r, w );
		else	wint ( query ( l, r, w ) ), putchar ( '\n' );
	}
}
}

int main () {
//	freopen ( "mag.in", "r", stdin );
//	freopen ( "mag-own.out", "w", stdout );
//	freopen ( "magic.in", "r", stdin );
//	freopen ( "magic.out", "w", stdout );
	mySpace :: main ();
	return 0;
}

∆ LOC20004 抄作业 - AC

$O(2^{n}n)$ 带个 $\frac{1}{2}$ 的常数，就是枚举每一位。然后因为画出来是个有向连通图，所以有正确性。

/* Clearink */

#include <cstdio>

namespace mySpace {
#define LL long long

const int MAXN = ( 1 << 22 ) + 5;

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

int n, a[MAXN];
bool vis[MAXN];

void main () {
	scanf ( "%d", &n ); int upper = 1 << n;
	a[0] = 1, vis[1] = vis[0] = 1;
	wint ( a[0] );
	for ( int i = 1; i < upper; ++ i ) {
		for ( int j = 0; j < n; ++ j ) {
			if ( ! vis[a[i - 1] ^ ( 1 << j )] ) {
				vis[a[i - 1] ^ ( 1 << j )] = 1;
				a[i] = a[i - 1] ^ ( 1 << j );
				break;
			}
		}
		putchar ( ' ' ), wint ( a[i] );
	}
}
}

int main () {
//	freopen ( "work.in", "r", stdin );
//	freopen ( "work.out", "w", stdout );
	mySpace :: main ();
	return 0;
}

∆ LOC3563 最大流 - AC

最大流板。

/* okay | there's been */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 200 + 5, MAXM = 5000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXM * 2];

int n, m, s, t, bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void makeEdge ( const int u, const int v, const LL w ) { as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt; }

bool bfs () {
	for ( int i = 1; i <= n; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, 1e18 ) ) ;
	return res;
}

void main () {
	n = rint (), m = rint (), s = rint (), t = rint ();
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint (); LL w = rint ();
		makeEdge ( u, v, w ), makeEdge ( v, u, 0 );
	}
	printf ( "%lld\n", calcMXflow () );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ USACO93 Drainage Ditches - AC

最大流板。

/* okay | there's been */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 200 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXN * 2];

int n, m, bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void makeEdge ( const int u, const int v, const LL w ) { as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt; }

bool bfs () {
	for ( int i = 1; i <= n; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = 1, lav[1] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[n];
}

LL dfs ( const int u, LL in ) {
	if ( u == n )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( 1, 1e18 ) ) ;
	return res;
}

void main () {
	m = rint (), n = rint ();
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint (); LL w = rint ();
		makeEdge ( u, v, w ), makeEdge ( v, u, 0 );
	}
	printf ( "%lld\n", calcMXflow () );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ LOC5744 The Perfect Stall - AC

最大流 / 二分图板。

/* okay | there's been */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 500 + 5, MAXM = MAXN * MAXN;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXM * 2];

int n, m, s, t, bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void makeEdge ( const int u, const int v, const LL w ) { as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt; }

bool bfs () {
	for ( int i = 1; i <= n + m + 3; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	continue;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( w, in ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, 1e18 ) ) ;
	return res;
}

void main () {
	n = rint (), m = rint (), s = 1, t = n + m + 3;
	for ( int i = 2; i <= n + 1; ++ i )	makeEdge ( s, i, 1 ), makeEdge ( i, s, 0 );
	for ( int _ = 1; _ <= n; ++ _ ) {
		int u = _ + 1, e = rint ();
		for ( int i = 1; i <= e; ++ i ) {
			int v = rint () + n + 2;
			makeEdge ( u, v, 1 );
			makeEdge ( v, u, 0 );
		}
	}
	for ( int i = n + 3; i <= n + m + 2; ++ i )	makeEdge ( i, t, 1 ), makeEdge ( t, i, 0 );
	printf ( "%lld\n", calcMXflow () );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ LOC8643 奶牛食品 - AC

最大流板。

/* okay | there's been */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 500 + 5, MAXM = MAXN * MAXN;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXM * 2];

int n, f, d, s, t, bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void addE ( const int u, const int v, const LL w ) { as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt; }

bool bfs () {
	for ( int i = 0; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, 1e18 ) ) ;
	return res;
}

void main () {
	n = rint (), f = rint (), d = rint ();
	s = 1, t = n + n + f + d + 2;
	for ( int i = 2; i <= f + 1; ++ i )	addE ( s, i, 1 ), addE ( i, s, 0 );
	for ( int i = f + 2; i <= n + f + 1; ++ i )	addE ( i, i + n, 1 ), addE ( i + n, i, 0 );
	for ( int $ = 1; $ <= n; ++ $ ) {
		int u = $ + f + 1, ff = rint (), dd = rint ();
		for ( int i = 1; i <= ff; ++ i ) {
			int v = rint () + 1;
			addE ( v, u, 1 ), addE ( u, v, 0 );
		}
		for ( int i = 1; i <= dd; ++ i ) {
			int v = rint () + f + n + n + 1;
			addE ( u + n, v, 1 ), addE ( v, u + n, 0 );
		}
	}
	for ( int i = n + n + f + 2; i <= n + n + f + d + 1; ++ i )	addE ( i, t, 1 ), addE ( t, i, 0 );
	printf ( "%lld\n", calcMXflow () );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ LOC4051 SDOI2015 星际战争 - AC

二分答案+最大流。

/* Clearink */

#include <cstdio>

namespace mySpace {
const double EPS = 1e-8, INF = 1e18;
const int MAXN = 100 + 5;

inline int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T ABS ( const _T x ) { return x > 0 ? x : -x; }
template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	double wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const double c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXN * MAXN * 2];

double sum;
int n, m, s, t, a[MAXN], b[MAXN], eds[MAXN][MAXN], bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

inline void addE ( const int u, const int v, const double w ) {
	as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt;
	as[++ cnt] = GraphSet ( u, bgn[v], 0 ), bgn[v] = cnt;
}

inline bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; double w = as[i].wt;
			if ( ABS ( w ) < EPS || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

inline double dfs ( const int u, double in ) {
	if ( u == t )	return in;
	double out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ABS ( in ) < EPS )	break;
		int v = as[i].to; double w = as[i].wt;
		if ( ABS ( w ) < EPS || lav[v] != lav[u] + 1 )	continue;
		double ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ABS ( out ) < EPS )	lav[u] = 0;
	return out;
}

inline double calcMXflow () {
	double res = 0;
	for ( ; bfs (); res += dfs ( s, INF ) ) ;
	return res;
}

inline void clrbook () { cnt = 1; for ( int i = s; i <= t; ++ i )	bgn[i] = 0; }
inline bool chkok ( const double tim ) {
	clrbook ();
	for ( int i = 1; i <= n; ++ i )	addE ( 1, i + 1, a[i] );
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			if ( eds[j][i] )	addE ( i + 1, j + n + 1, INF );
		}
	}
	for ( int i = 1; i <= m; ++ i )	addE ( i + n + 1, t, b[i] * tim );
	return ABS ( calcMXflow () - sum ) < EPS;
}

inline double brySrch ( double l, double r ) {
	for ( ; l + EPS < r; ) {
		double mid = ( l + r ) / 2;
		if ( chkok ( mid ) )	r = mid;
		else	l = mid;
	}
	return r;
}

void main () {
	n = rint (), m = rint ();
	for ( int i = 1; i <= n; ++ i )	sum += ( a[i] = rint () );
	for ( int i = 1; i <= m; ++ i )	b[i] = rint ();
	s = 1, t = n + m + 2;
	for ( int i = 1; i <= m; ++ i ) {
		for ( int j = 1; j <= n; ++ j )	eds[i][j] = rint ();
	}
	printf ( "%lf\n", brySrch ( 0, INF ) );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ LOC5123 网络流 24 题圆桌聚餐 - AC

最大流板。

/* Clearink */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 100000 + 5, MAXM = 5e7 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXN * 2];

int n, m, s, t, r[MAXN], c[MAXN], bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void addE ( const int u, const int v, const int w ) {
	as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt;
	as[++ cnt] = GraphSet ( u, bgn[v], 0 ), bgn[v] = cnt;
}

bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, 1e18 ) ) ;
	return res;
}

void main () {
	m = rint (), n = rint (); LL sum = 0;
	for ( int i = 2; i <= m + 1; ++ i )	sum += ( r[i] = rint () );
	for ( int i = m + 2; i <= n + m + 1; ++ i )	c[i] = rint ();
	s = 1, t = m + n + 2;
	for ( int i = 2; i <= m + 1; ++ i )	addE ( s, i, r[i] );
	for ( int i = 2; i <= m + 1; ++ i ) {
		for ( int j = m + 2; j <= n + m + 1; ++ j )	addE ( i, j, 1 );
	}
	for ( int i = m + 2; i <= n + m + 1; ++ i )	addE ( i, t, c[i] );
	LL mxf = calcMXflow ();
	if ( mxf == sum ) {
		wint ( 1 ), putchar ( '\n' );
		for ( int _ = 2; _ <= m + 1; ++ _ ) {
			int u = _;
			for ( int i = bgn[u]; i; i = as[i].nx ) {
				int v = as[i].to; LL w = as[i].wt;
				if ( v >= m + 2 && v <= n + m + 1 && ! w )	wint ( v - m - 1 ), putchar ( ' ' );
			}
			putchar ( '\n' );
		}
	}
	else	wint ( 0 ), putchar ( '\n' );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

/* 1     2~m+1  m+2~n+m+1 n+m+2 */
/* S ri company 1 table ci T */

∆ LOC5123 网络流 24 题圆桌聚餐 - AC

最大流板。

/* Clearink */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 100000 + 5, MAXM = 5e7 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXN * 2];

int n, m, s, t, r[MAXN], c[MAXN], bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void addE ( const int u, const int v, const int w ) {
	as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt;
	as[++ cnt] = GraphSet ( u, bgn[v], 0 ), bgn[v] = cnt;
}

bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, 1e18 ) ) ;
	return res;
}

void main () {
	m = rint (), n = rint (); LL sum = 0;
	for ( int i = 2; i <= m + 1; ++ i )	sum += ( r[i] = rint () );
	for ( int i = m + 2; i <= n + m + 1; ++ i )	c[i] = rint ();
	s = 1, t = m + n + 2;
	for ( int i = 2; i <= m + 1; ++ i )	addE ( s, i, r[i] );
	for ( int i = 2; i <= m + 1; ++ i ) {
		for ( int j = m + 2; j <= n + m + 1; ++ j )	addE ( i, j, 1 );
	}
	for ( int i = m + 2; i <= n + m + 1; ++ i )	addE ( i, t, c[i] );
	LL mxf = calcMXflow ();
	if ( mxf == sum ) {
		wint ( 1 ), putchar ( '\n' );
		for ( int _ = 2; _ <= m + 1; ++ _ ) {
			int u = _;
			for ( int i = bgn[u]; i; i = as[i].nx ) {
				int v = as[i].to; LL w = as[i].wt;
				if ( v >= m + 2 && v <= n + m + 1 && ! w )	wint ( v - m - 1 ), putchar ( ' ' );
			}
			putchar ( '\n' );
		}
	}
	else	wint ( 0 ), putchar ( '\n' );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

/* 1     2~m+1  m+2~n+m+1 n+m+2 */
/* S ri company 1 table ci T */

∆ P4539 [SCOI2006] zh_tree - AC

\text{ANS}=\min\{\frac{1}{S}\times k\sum_{i = 1}^n d_{i}(r_{i}+1)+S\times c\}

我们能控制的只有 $r_{i}$ ，然而 $r_{i}$ 和 $d_{i}$ 是相关的，那么这个东西其实没什么用。

设 $f_{l,r}$ 为把区间 $[l,r]$ 建成一棵子树的代价。

#include <cstdio>
#include <cstring>

namespace mySpace {
const int MAXN = 30 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

int n;
double k, c, f[MAXN][MAXN], d[MAXN], S, pS[MAXN][MAXN];

void main () {
	n = rint (), scanf ( "%lf%lf", &k, &c );
	for ( int i = 1; i <= n; ++ i )	S += ( d[i] = rint () );
	memset ( f, 0x7f, sizeof ( f ) );
	for ( int i = 1; i <= n; ++ i )	f[i][i] = d[i] * ( k + c );
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = i; j <= n; ++ j )	pS[i][j] = pS[i][j - 1] + k * d[j];
	}
	for ( int dis = 2; dis <= n; ++ dis ) {
		for ( int i = 1, j = dis; j <= n; ++ i, ++ j ) {
			f[i][j] = MIN ( f[i][j - 1] + c * d[j], f[i + 1][j] + c * d[i] );
			for ( int k = i + 1; k < j; ++ k )	f[i][j] = MIN ( f[i][j], f[i][k - 1] + f[k + 1][j] + c * d[k] );
			f[i][j] += pS[i][j];
		}
	}
	printf ( "%.3lf\n", ( double )f[1][n] / S );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ P3736 [HAOI2016]字符合并 - AC

旧题重做。

我们先把能合的都合起来，合完后展开。可以发现这些区间是不相交的。

设 $f_{i,j,S}$ 表示区间 $[i,j]$ 合并后为 $S$ 的最大分数。

直接转移死有余辜。

我们可以发现合并一个区间 $[x,x+a(k-1)]$ 的时候，最后我们一定会把它弄成长度为 $1$ 。

进一步可以得到合并一个区间 $[l,r]$ 我们会把它合并成一个长度为 $(r-l)\bmod(k-1)+1$ 的区间。

则方程为：

f_{i,j,S}=\max\{f_{i,x,S}+f_{x+1,j,\empty}\}

特殊情况是区间可以直接被 $k$ 整除，特判算贡献即可。

#include <cstdio>
#include <cstring>

namespace mySpace {
typedef long long LL;

const LL INF = 4485090715960753727;
const int MAXN = 300 + 5, MAXK = ( 1 << 8 ) + 8;

int rint ( bool fl = 0 ) {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () ) {
		x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
		if ( fl )	break;
	}
	return x * f;
}

template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }

int n, k, c[MAXK], w[MAXK], a[MAXN], upper;
LL f[MAXN][MAXN][MAXK];

void MXtaken () { memset ( f, -0x3f, sizeof ( f ) ); }

void main () {
	n = rint (), k = rint (), upper = ( 1 << k );
	for ( int i = 1; i <= n; ++ i )	a[i] = rint ( 1 );
	for ( int i = 0; i < upper; ++ i )	c[i] = rint (), w[i] = rint ();
	MXtaken ();
	for ( int i = 1; i <= n; ++ i )	f[i][i][a[i]] = 0;
	for ( int d = 2; d <= n; ++ d ) {
		for ( int i = 1, j = d; j <= n; ++ i, ++ j ) {
			int xxx = ( d - 1 ) % ( k - 1 );
			if ( ! xxx )	xxx = k - 1;
			for ( int o = j - 1; o >= i; o -= k - 1 ) {
				int tupper = ( 1 << xxx );
				for ( int S = 0; S < tupper; ++ S ) {
					f[i][j][S << 1] = MAX ( f[i][j][S << 1], f[i][o][S] + f[o + 1][j][0] );
					f[i][j][S << 1 | 1] = MAX ( f[i][j][S << 1 | 1], f[i][o][S] + f[o + 1][j][1] );
				}
			}
			if ( xxx == k - 1 ) {
				LL ar[2] = { -INF, -INF };
				for ( int S = 0; S < upper; ++ S )	ar[c[S]] = MAX ( ar[c[S]], f[i][j][S] + w[S] );
				f[i][j][0] = ar[0], f[i][j][1] = ar[1];
			}
		}
	}
	LL ans = -INF;
	for ( int i = 0; i < upper; ++ i )	ans = MAX ( ans, f[1][n][i] );
	printf ( "%lld\n", ans );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ AT2433 ケーキの切り分け２ (Cake 2) via JOI2015 Final T2 - IP

先行套路破环为链，可以知道蛋糕的选择一定是一个连续的区间。

设 $f_{i,j}$ 为 JOIくん当前选的区间。

然后分类讨论完。

#include <cstdio>
#include <cstring>

namespace mySpace {
typedef long long LL;

const int MAXN = 4000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }

int n, nn, a[MAXN];
LL f[MAXN][MAXN];

void main () {
	n = rint (), nn = n << 1;
	for ( int i = 1; i <= n; ++ i )	a[i] = a[i + n] = rint ();
	a[0] = a[n];
	for ( int i = 1; i <= nn; ++ i )	f[i][i] = a[i];
	for ( int d = 1; d < n; ++ d ) {
		for ( int i = 1, j = d + 1; j <= nn; ++ i, ++ j ) {
			if ( d & 1 ) {
				if ( a[i - 1] < a[j] || d == n - 1 ) {
					if ( a[i] > a[j + 1] || d == n - 1 )	f[i][j] = MAX ( f[i][j - 1], f[i + 1][j] );
					else	f[i][j] = f[i][j - 1];
				}
				else {
					if ( a[i] > a[j + 1] || d == n - 1 )	f[i][j] = f[i + 1][j];
					else	f[i][j] = f[i][j];
				}
			}
			else	f[i][j] = MAX ( f[i + 1][j] + a[i], f[i][j - 1] + a[j] );
		}
	}
	LL ans = 0;
	for ( int i = 1; i <= n; ++ i )	ans = MAX ( ans, f[i][i + n - 1] );
	printf ( "%lld\n", ans );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ CF1296C Yet Another Walking Robot - AC

雪耻，猛然发现一年前的我是个 Div. 3 C 都做不来的煞笔。

跑一下出来的点，完了。

#include <map>
#include <cstdio>

using namespace std;

namespace mySpace {
typedef long long LL;

const int MAXN = 2e5 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

struct Point {
	int x, y;
	Point () : x ( 0 ), y ( 0 ) {}
	Point ( const int a, const int b ) : x ( a ), y ( b ) {}
	Point operator + ( const Point& other ) const { return Point ( x + other.x, y + other.y ); }
} as[MAXN];

map<LL, int> MP;
int n;
char s[MAXN];

LL has ( const Point pnt ) { return pnt.x * 2e5 + pnt.y; }

void main () {
	int brick = rint ();
	for ( ; brick; brick -- ) {
		n = rint (), scanf ( "%s", s + 1 );
		for ( int i = 1; i <= n; ++ i ) {
			char c = s[i];
			if ( c == 'L' )	as[i] = Point ( -1, 0 );
			else if ( c == 'R' )	as[i] = Point ( 1, 0 );
			else if ( c == 'U' )	as[i] = Point ( 0, 1 );
			else	as[i] = Point ( 0, -1 );
		}
		MP.clear ();
		int ans = 2e9, ansl = 0, ansr = 0;
		Point nowp; MP[has ( nowp )] = 0;
		for ( int i = 1; i <= n; ++ i ) {
			nowp = nowp + as[i];
			if ( MP.find ( has ( nowp ) ) != MP.end () ) {
				int ID = MP[has ( nowp )];
				if ( i - ID + 1 < ans )	ans = i - ID + 1, ansl = ID + 1, ansr = i;
				MP[has ( nowp )] = i;
			}
			else	MP[has ( nowp )] = i;
		}
		if ( ans == 2e9 )	wint ( -1 ), putchar ( '\n' );
		else {
			wint ( ansl ), putchar ( ' ' );
			wint ( ansr ), putchar ( '\n' );
		}
	}
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ P4689 Ynoi2016 这是我自己的发明 - AC

我首先认为这是 SNOI2017 一个简单的询问搬到树上。

我们传统地把此题分为两个 $\texttt{pass}$ ，一个询问，一个修改。

$\texttt{pass 1}$ ：询问

我直接按 一个简单的询问 的方法讲。~~其实是把以前的题解 copy 过来了~~。

由于是出现次数，满足区间加减性，所以我们可以这样表达 $\mathrm{get}(l,r,x)$ （省略 $x$ ）:

\mathrm{get}(l,r)=\mathrm{get}(1,r)-\mathrm{get}(1,l-1)

那么我们代进原式，化一波式子（ $\mathrm{get}(p)=\mathrm{get}(1,p,x)$ ）：

\sum_{i=1}^{\infty}\mathrm{get}(l_{1},r_{1},x)\times\mathrm{get}(l_{2},r_{2},x)

\sum_{i=1}^{\infty}(\mathrm{get}(1,r_{1})-\mathrm{get}(1,l_{1}-1))\times(\mathrm{get}(1,r_{2})-\mathrm{get}(1,l_{2}-1))

\sum_{i=1}^{\infty}\mathrm{get}(r_{1})\times\mathrm{get}(r_{2})-\mathrm{get}(r_{1})\times\mathrm{get}(l_{2}-1)-\mathrm{get}(l_{1}-1)\times\mathrm{get}(r_{2})+\mathrm{get}(l_{1}-1))\times\mathrm{get}(l_{2}-1)

\mathrm{let}\ F(x,y)=\sum_{d}\mathrm{get}(1,l,d)\times\mathrm{get}(1,r,d)

则答案为:

F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1)

考虑怎么更新，比如从 $l$ 更新到 $l+1$ ，则：

\mathrm{get(1,l)}\times\mathrm{get}(1,r)

\mathrm{get(1,l+1)}\times\mathrm{get}(1,r)

\mathrm{get(1,l)}\times\mathrm{get}(1,r)+\mathrm{cont}(a_{l})

其中 $\mathrm{cont}(a_{l})$ 表示 $a_{l}$ 的出现次数。

则我们就知道怎么更新了，由于我们维护和的是前缀信息，所以姿势和普通莫队有点不一样。

维护两个数组 cntl[x] 和 cntr[y] 表示答案式子

F(r_{1},r_{2})-F(r_{1},l_{2}-1)-F(l_{1}-1,r_{2})+F(l_{1}-1,l_{2}-1)

子树的话直接 DFS 拍到序列上。

$\texttt{pass 2}$ ：修改

现在我们面临着查询操作我们是用莫队整的，但这个修改貌似不单纯。~~其实也是从树剖模板缝合过来的~~。

分类讨论，设我们当前要换的根为 $rt$ ，现在来处理询问，设查询的节点为 $u$ ， $\text{LCA}(u,v)$ 为节点 $u$ 和节点 $v$ 的最近公共祖先。

- 如果 $rt=u$ ，则我们直接对整棵树进行查询。
- 如果 $\text{LCA}(u,rt)\neq u$ ，此时修改不影响查询。
- 如果 $\text{LCA}(u,rt)=u$ ，此时 $rt$ 在 $u$ 的子树里，那么需要查询的地方就很明确了，后面的步骤显然。

于是我们不需要实际的去处理这个修改，然后就可以直接莫队了。

（整体感觉是个原题+假上树+树剖模板的缝合题）

/* Clearink */

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long LL;

const int MAXN = 5e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<class _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<class _T> void swapp ( _T& x, _T& y ) { _T w = x; x = y; y = w; }

struct GraphSet {
	int to, nx;
	GraphSet () : to ( 0 ), nx ( 0 ) {}
	GraphSet ( const int a, const int b ) : to ( a ), nx ( b ) {}
} asg[MAXN * 2];

struct Quest {
	int l, r, ID, x;
	Quest () : l ( 0 ), r ( 0 ), ID ( 0 ), x ( 0 ) {}
	Quest ( const int a, const int b, const int c, const int d ) : l ( a ), r ( b ), ID ( c ), x ( d ) {}
} asq[MAXM * 8], itls[MAXN];

LL cur = 0, ans[MAXM], buc1[MAXN], buc2[MAXN];
int rt, pos[MAXN], blo = 320, col[MAXN], freq;
int n, m, bgn[MAXN], cnt, sjc, segl[MAXN], segr[MAXN], kfa[MAXN][21], a[MAXN], dept[MAXN], pri[MAXN], len;

void addE ( const int u, const int v ) { asg[++ cnt] = GraphSet ( v, bgn[u] ), bgn[u] = cnt; }
bool existcmp ( const Quest& one, const Quest& ano ) { return pos[one.l] == pos[ano.l] ? one.r < ano.r : one.l < ano.l; }

void dfs ( const int u, const int lst ) {
	kfa[u][0] = lst, dept[u] = dept[lst] + 1;
	segl[u] = ++ sjc, col[sjc] = a[u];
	for ( int i = 1; i <= 20; ++ i )	kfa[u][i] = kfa[kfa[u][i - 1]][i - 1];
	for ( int i = bgn[u]; i; i = asg[i].nx ) {
		int v = asg[i].to;
		if ( v == lst )	continue;
		dfs ( v, u );
	}
	segr[u] = sjc;
}

int calcKAC ( int u, int k ) {
	for ( int i = 20; ~ i; -- i ) {
		if ( k >= ( 1 << i ) )	k -= ( 1 << i ), u = kfa[u][i];
	}
	return u;
}

int calcLCA ( int u, int v ) {
	if ( dept[u] < dept[v] )	swapp ( u, v );
	for ( int i = 20; ~ i; -- i ) {
		if ( dept[kfa[u][i]] >= dept[v] )	u = kfa[u][i];
	}
	if ( u == v )	return u;
	for ( int i = 20; ~ i; -- i ) {
		if ( kfa[u][i] != kfa[v][i] )	u = kfa[u][i], v = kfa[v][i];
	}
	return kfa[u][0];
}

void initial () {
	for ( int i = 1; i <= n; ++ i )	pos[i] = ( i - 1 ) / blo + 1;
	sort ( pri + 1, pri + 1 + n );
	len = unique ( pri + 1, pri + 1 + n ) - pri - 1;
	for ( int i = 1; i <= n; ++ i )	a[i] = lower_bound ( pri + 1, pri + 1 + len, a[i] ) - pri;
	dfs ( 1, 0 );
}

void splitASdrug ( const int u, int& ils ) {
	if ( u == rt )	itls[++ ils] = Quest ( 1, n, 0, 0 );
	else {
		int lca = calcLCA ( u, rt );
		if ( lca != u )	itls[++ ils] = Quest ( segl[u], segr[u], 0, 0 );
		else {
			int ar = calcKAC ( rt, dept[rt] - dept[u] - 1 );
			if ( 1 <= segl[ar] - 1 )	itls[++ ils] = Quest ( 1, segl[ar] - 1, 0, 0 );
			if ( segr[ar] + 1 <= n )	itls[++ ils] = Quest ( segr[ar] + 1, n, 0, 0 );
		}
	}
}

void transASsub ( const int l1, const int r1, const int l2, const int r2, const int ID ) {
	asq[++ m] = Quest ( r1, r2, ID, 1 ), asq[++ m] = Quest ( r1, l2 - 1, ID, -1 );
	asq[++ m] = Quest ( l1 - 1, r2, ID, -1 ), asq[++ m] = Quest ( l1 - 1, l2 - 1, ID, 1 );
}

void transASmany ( const int l, const int r ) {
	++ freq;
	int ils = 0; splitASdrug ( l, ils );
	int aim = ils; splitASdrug ( r, ils );
	for ( int i = 1; i <= aim; ++ i ) {
		for ( int j = aim + 1; j <= ils; ++ j )	transASsub ( itls[i].l, itls[i].r, itls[j].l, itls[j].r, freq );
	}
}

void add1 ( const int x ) { cur += buc2[col[x]], buc1[col[x]] ++; }
void add2 ( const int x ) { cur += buc1[col[x]], buc2[col[x]] ++; }
void sub1 ( const int x ) { cur -= buc2[col[x]], buc1[col[x]] --; }
void sub2 ( const int x ) { cur -= buc1[col[x]], buc2[col[x]] --; }
void captainMO () {
	int nowl = 0, nowr = 0;
	for ( int i = 1; i <= m; ++ i ) {
		for ( ; nowl < asq[i].l; add1 ( ++ nowl ) ) ;
		for ( ; nowr < asq[i].r; add2 ( ++ nowr ) ) ;
		for ( ; nowl > asq[i].l; sub1 ( nowl -- ) ) ;
		for ( ; nowr > asq[i].r; sub2 ( nowr -- ) ) ;
		ans[asq[i].ID] += cur * asq[i].x;
	}
}

int main () {
	n = rint (); int _waste_ = rint ();
	for ( int i = 1; i <= n; ++ i )	a[i] = pri[i] = rint ();
	for ( int i = 1; i < n; ++ i ) {
		int u = rint (), v = rint ();
		addE ( u, v ), addE ( v, u );
	}
	initial (), rt = 1;
	for ( int i = 1; i <= _waste_; ++ i ) {
		int c = rint (), x, y;
		if ( c == 1 )	rt = rint ();
		else	x = rint (), y = rint (), transASmany ( x, y );
	}
	sort ( asq + 1, asq + 1 + m, existcmp ), captainMO ();
	for ( int i = 1; i <= freq; ++ i )	wint ( ans[i] ), putchar ( '\n' );
	return 0;
}

∆ P6701 [POI1997] Genotype - AC

反过来想，相当于就是让一个 Genotype 通过合并得到的最短字符串（全为 “S”）长度。

然后就是和“[HAOI2016]字符合并”差不多。

设 $f_{l,r}$ 表示合并区间 $[l,r]$ 能缩成个什么东西，字符集大小 26 随便存。

完了。

#include <cstdio>
#include <cstring>

const int INF = 0x3f3f3f3f;
const int MAXN = 100 + 5;

int n, waste, rul[30][30], f[MAXN][MAXN], tra[MAXN][MAXN];
char s[MAXN];

int trans ( const char x ) { return x - 'A' + 1; }
int MIN ( const int x, const int y ) { return x < y ? x : y; }

int main () {
	scanf ( "%d", &waste );
	for ( int i = 1; i <= waste; ++ i ) {
		scanf ( "%s", s + 1 );
		rul[trans ( s[2] )][trans ( s[3] )] |= ( 1 << trans ( s[1] ) );
	}
	for ( scanf ( "%d", &waste ); waste; waste -- ) {
		scanf ( "%s", s + 1 ), n = strlen ( s + 1 );
		memset ( tra, 0, sizeof ( tra ) ), memset ( f, 0x3f, sizeof ( f ) );
		for ( int i = 1; i <= n; ++ i ) {
			if ( s[i] == 'S' )	f[i][i] = 1;
			tra[i][i] |= ( 1 << trans ( s[i] ) );
		}
		for ( int d = 1; d <= n; ++ d ) {
			for ( int i = 1, j = d; j <= n; ++ i, ++ j ) {
				for ( int k = i; k <= j; ++ k ) {
					f[i][j] = MIN ( f[i][j], f[i][k] + f[k + 1][j] );
					for ( int c1 = 1; c1 <= 26; ++ c1 ) {
						for ( int c2 = 1; c2 <= 26; ++ c2 ) {
							if ( ( tra[i][k] & ( 1 << c1 ) ) && ( tra[k + 1][j] & ( 1 << c2 ) ) )	tra[i][j] |= rul[c1][c2];
						}
					}
				}
				if ( tra[i][j] & ( 1 << 19 ) )	f[i][j] = 1;
			}
		}
		if ( f[1][n] >= INF )	puts ( "NIE" );
		else	printf ( "%d\n", f[1][n] );
	}
	return 0;
}

∆ P4194 矩阵 - AC

考虑二分答案。

令 $h_{i}=\sum a_{i,j},w_{i}=\sum a_{j,i}$ ，设当前二分的值为 $x$ 。

如果这个 $x$ 可行，应该要对 $|\sum a_{i,j}-b_{i,j}|\le x$ 分类讨论，嗯。

然后出来范围就是 $\sum b_{i,j}$ 的范围是 $[-x,x]+h_{i}$ ，同理可得列的情况，然后就可以上瘤子了。

对矩阵的每一行、每一列开一个点，建超源超汇。 $S$ 向每一行连 $[h_{i}-x,h_{i}+x]$ ，每一列向 $T$ 连 $[w_{i}-x,w_{i}+x]$ ，对应的行列之间连个 $[L,R]$ 。

完了。

#include <cstdio>
#define int long long

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, s, t, supS, supT, head[MAXN], ecnt = 1, lav[MAXN], ali[MAXN], npts, L, R, h[MAXN], w[MAXN], cur[MAXN], pntS[MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs ( const int s, const int t ) {
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0, cur[i] = head[i];
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, const int aimS, int flow ) {
	if ( u == aimS )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, aimS, MIN ( flow - used, w ) );
		graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
		if ( flow == used )	break;
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int cS, const int cT ) {
	int res = 0;
	for ( ; bfs ( cS, cT ); res += dfs ( cS, cT, INF ) ) ;
	return res;
}

bool check ( const int x ) {
	npts = n * m + n + m, ecnt = 1;
	for ( int i = 1; i <= npts + 10; ++ i )	head[i] = pntS[i] = 0;
	s = ++ npts, t = ++ npts, supS = ++ npts, supT = ++ npts;
	for ( int i = 1; i <= n; ++ i ) {
		int lwr = h[i] - x, upr = h[i] + x;
		link ( s, i + n * m, upr - lwr );
		pntS[s] -= lwr, pntS[i + n * m] += lwr;
	}
	for ( int i = 1; i <= m; ++ i ) {
		int lwr = w[i] - x, upr = w[i] + x;
		link ( i + n * m + n, t, upr - lwr );
		pntS[i + n * m + n] -= lwr, pntS[t] += lwr;
	}
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			int lwr = L, upr = R;
			link ( i + n * m, j + n * m + n, upr - lwr );
			pntS[i + n * m] -= lwr, pntS[j + n * m + n] += lwr;
		}
	}
	int all = 0;
	for ( int i = 1; i <= npts - 2; ++ i ) {
		if ( pntS[i] > 0 )	link ( supS, i, pntS[i] ), all += pntS[i];
		else	link ( i, supT, - pntS[i] );
	}
	link ( t, s, INF );
	return calcMXflow ( supS, supT ) == all;
}

int solve ( int l, int r ) {
	int res = 0;
	for ( ; l <= r; ) {
		int mid = ( l + r ) >> 1;
		if ( check ( mid ) )	r = mid - 1, res = mid;
		else	l = mid + 1;
	}
	return res;
}

signed main () {
	n = rint (), m = rint ();
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1, x; j <= m; ++ j )	x = rint (), h[i] += x, w[j] += x;
	}
	L = rint (), R = rint ();
	printf ( "%d\n", solve ( 0, INF ) );
	return 0;
}

∆ P4843 清理雪道 - AC

流板。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 200 + 5, MAXM = MAXN * MAXN;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, s, t, supS, supT, head[MAXN], ecnt = 1, lav[MAXN], ali[MAXN], pntS[MAXN], npts, cur[MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs ( const int s, const int t ) {
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0, cur[i] = head[i];
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, const int aimS, int flow ) {
	if ( u == aimS )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, aimS, MIN ( flow - used, w ) );
		graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
		if ( flow == used )	break;
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int cS, const int cT ) {
	int res = 0;
	for ( ; bfs ( cS, cT ); res += dfs ( cS, cT, INF ) ) ;
	return res;
}

int main () {
	npts = n = rint (), s = ++ npts, t = ++ npts;
	supS = ++ npts, supT = ++ npts;
	for ( int _ = 1; _ <= n; ++ _ ) {
		m = rint (); int u = _;
		for ( int i = 1; i <= m; ++ i ) {
			int v = rint ();
			link ( u, v, INF ), pntS[u] --, pntS[v] ++;
		}
	}
	for ( int i = 1; i <= n; ++ i )	link ( s, i, INF ), link ( i, t, INF );
	int all = 0;
	for ( int i = 1; i <= npts; ++ i ) {
		if ( pntS[i] > 0 )	link ( supS, i, pntS[i] ), all += pntS[i];
		else	link ( i, supT, - pntS[i] );
	}
	link ( t, s, INF ), calcMXflow ( supS, supT );
	int tmp = graph[ecnt].cst;
	head[s] = graph[head[s]].nxt, head[t] = graph[head[t]].nxt;
	printf ( "%d\n", tmp - calcMXflow ( t, s ) );
	return 0;
}

∆ POJ3204 伊基的故事 I - 道路重建 - AC

流板。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 500 + 5, MAXM = 5000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

bool vstfrwd[MAXN], vstbkwd[MAXN];
int n, m, s, t, head[MAXN], ecnt = 1, lav[MAXN], ali[MAXN], npts, cur[MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs () {
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0, cur[i] = head[i];
	ali[1] = s, lav[s] = 1;
	int nowl = 1, nowr = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, int lin ) {
	if ( u == t )	return lin;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, MIN ( lin - used, w ) );
		graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
		if ( used == lin )	break;
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

void augment () { for ( ; bfs (); dfs ( s, INF ) ) ; }

void srchfrwd () {
	int nowl = 1, nowr = 1;
	ali[1] = s, vstfrwd[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! vstfrwd[v] )	vstfrwd[ali[++ nowr] = v] = 1;
		}
	}
}

void srchbkwd () {
	int nowl = 1, nowr = 1;
	ali[1] = t, vstbkwd[t] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i ^ 1].cst;
			if ( w && ! vstbkwd[v] )	vstbkwd[ali[++ nowr] = v] = 1;
		}
	}
}

int main () {
	npts = n = rint (), m = rint (), s = 1, t = n;
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint (), w = rint ();
		link ( u, v, w );
	}
	augment (), srchfrwd (), srchbkwd ();
	int ans = 0;
	for ( int i = 2; i <= ecnt; i += 2 ) {
		if ( vstfrwd[graph[i ^ 1].to] && vstbkwd[graph[i].to] )	ans ++;
	}
	printf ( "%d\n", ans );
	return 0;
}

∆ LOC26288 多源汇最大流 - AC

流板。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e4 + 5, MAXM = 1e5 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2 + 5];

int n, m, cs, ct, s, t, head[MAXN], ecnt = 1, lav[MAXN], ali[MAXN], npts, cur[MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs () {
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0, cur[i] = head[i];
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, int flow ) {
	if ( u == t )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to	, w = graph[i].cst;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, MIN ( flow - used, w ) );
		graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
		if ( used == flow )	break;
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow () {
	int res = 0;
	for ( ; bfs (); res += dfs ( s, INF ) ) ;
	return res;
}

int main () {
	npts = n = rint (), m = rint (), cs = rint (), ct = rint ();
	s = ++ npts, t = ++ npts;
	for ( int i = 1; i <= cs; ++ i )	link ( s, rint (), INF );
	for ( int i = 1; i <= ct; ++ i )	link ( rint (), t, INF );
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint (), w = rint ();
		link ( u, v, w );
	}
	printf ( "%d\n", calcMXflow () );
	return 0;
}

∆ LOC26287 有源汇有上下界最小流 - AC

流板。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } as[MAXM * 2];

int n, m, s, t, head[MAXN], ecnt = 1, lav[MAXN], ali[MAXN], all, pntS[MAXN], npts, cur[MAXN];

void dolink ( const int u, const int v, const int w ) { as[++ ecnt] = { v, head[u], w }, head[u] = ecnt; }
void link ( const int u, const int v, const int w ) { dolink ( u, v, w ), dolink ( v, u, 0 ); }

bool bfs ( const int s, const int t ) {
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0, cur[i] = head[i];
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = as[i].nxt ) {
			int v = as[i].to, w = as[i].cst;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, const int aimS, int flow ) {
	if ( u == aimS )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = as[i].nxt ) {
		if ( ! flow )	break;
		int v = as[i].to, w = as[i].cst;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, aimS, MIN ( flow - used, w ) );
		as[i].cst -= ret, as[i ^ 1].cst += ret, used += ret;
		if ( used == flow )	break;
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int cS, const int cT ) {
	int res = 0;
	for ( ; bfs ( cS, cT ); res += dfs ( cS, cT, INF ) ) ;
	return res;
}

int main () {
	npts = n = rint (), m = rint (), s = rint (), t = rint ();
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint (), lwr = rint (), upr = rint ();
		link ( u, v, upr - lwr ), pntS[u] -= lwr, pntS[v] += lwr;
	}
	const int S = ++ npts, T = ++ npts;
	for ( int i = 1; i <= n; ++ i ) {
		if ( pntS[i] > 0 )	link ( S, i, pntS[i] ), all += pntS[i];
		else	link ( i, T, - pntS[i] );
	}
	link ( t, s, INF );
	if ( calcMXflow ( S, T ) == all ) {
		int tmp = as[ecnt].cst;
		head[t] = as[head[t]].nxt, head[s] = as[head[s]].nxt;
		wint ( tmp - calcMXflow ( t, s ) ), putchar ( '\n' );
	}
	else	puts ( "please go home to sleep" );
	return 0;
}

∆ LOC9371 网络流 24 题最小路径覆盖问题 - AC

流板。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 400 + 5, MAXM = 6000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx, wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const int c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[( MAXN + MAXM ) * 4];

int n, m, s, t, head[MAXN], cnt = 1, lav[MAXN], ali[MAXN], sts[MAXN], nxt[MAXN];

void addE ( const int u, const int v, const int w ) {
	as[++ cnt] = GraphSet ( v, head[u], w ), head[u] = cnt;
	as[++ cnt] = GraphSet ( u, head[v], 0 ), head[v] = cnt;
}

bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = head[u]; i; i = as[i].nx ) {
			int v = as[i].to, w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, int in ) {
	if ( u == t )	return in;
	int out = 0;
	for ( int i = head[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to, w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, MIN ( in, w ) );
		if ( ! ret )	continue;
		nxt[u] = v; if ( u != s )	sts[u - n] = 1;
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

int calcMXflow () {
	int res = 0;
	for ( ; bfs (); res += dfs ( s, INF ) ) ;
	return res;
}

int main () {
	n = rint (), m = rint (), s = 0, t = n * 2 + 1;
	for ( int i = 1; i <= n; ++ i )	addE ( s, i, 1 ), addE ( i + n, t, 1 );
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint ();
		addE ( u, v + n, 1 );
	}
	int ret = calcMXflow ();
	for ( int _ = 1; _ <= n; ++ _ ) {
		int u = _;
		if ( sts[u] )	continue;
		wint ( u ), putchar ( ' ' );
		for ( ; nxt[u]; u = nxt[u] - n ) {
			if ( nxt[u] == t )	break;
			wint ( nxt[u] - n ), putchar ( ' ' );
		}
		putchar ( '\n' );
	}
	wint ( n - ret ), putchar ( '\n' );
	return 0;
}

∆ LOC26280 无源汇上下界可行流 - AC

流板。

#include <cstdio>

typedef long long LL;

const LL INF = 1e18;
const int MAXN = 200 + 5, MAXM = 10200 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[( MAXN + MAXM ) * 2];

struct EdgeSet {
	int u, v;
	LL wtl, wtr;
	EdgeSet () : u ( 0 ), v ( 0 ), wtl ( 0 ), wtr ( 0 ) {}
	EdgeSet ( const int a, const int b, const LL c, const LL d ) : u ( a ), v ( b ), wtl ( c ), wtr ( d ) {}
} eds[MAXM];

int n, m, s, t, bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];
LL ups[MAXN], outs[MAXN], all;

void addE ( const int u, const int v, const LL w ) {
	as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt;
	as[++ cnt] = GraphSet ( u, bgn[v], 0 ), bgn[v] = cnt;
}

bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, INF ) ) ;
	return res;
}

int main () {
	n = rint (), m = rint (), s = 0, t = n + 1;
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint ();
		LL lower = rint (), upper = rint ();
		eds[i] = EdgeSet ( u, v, lower, upper );
	}
	for ( int i = 1; i <= m; ++ i )	ups[eds[i].v] += eds[i].wtl, outs[eds[i].u] += eds[i].wtl;
	for ( int i = 1; i <= m; ++ i )	addE ( eds[i].u, eds[i].v, eds[i].wtr - eds[i].wtl );
	for ( int i = 1; i <= n; ++ i ) {
		if ( ups[i] >= outs[i] )	addE ( s, i, ups[i] - outs[i] ), all += ups[i] - outs[i];
		else	addE ( i, t, outs[i] - ups[i] );
	}
	LL ret = calcMXflow ();
	if ( ret == all ) {
		puts ( "YES" );
		for ( int i = 2; i <= ( m << 1 | 1 ); i += 2 )	wint ( eds[i >> 1].wtl + as[i ^ 1].wt ), putchar ( '\n' );
	}
	else	puts ( "NO" );
	return 0;
}

∆ LOC3097 网络流 24 题最长递增子序列 - AC

懒得写了。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=1e9;
int n,s,t,a[510],head[510],cntot=1,f[510],to[250010],nxt[250010],val[250010],dep[510],ali[510],len;
void addedge(int one,int ano,int lav)
{
	to[++cntot]=ano;
	nxt[cntot]=head[one];
	val[cntot]=lav;
	head[one]=cntot;
	to[++cntot]=one;
	nxt[cntot]=head[ano];
	val[cntot]=0;
	head[ano]=cntot;
}
int getstr()
{
	f[1]=1;
	for(int i=2;i<=n;++i)
	{
		for(int j=0;j<i;++j)
		{
			if(a[j]<=a[i])	f[i]=max(f[i],f[j]+1);
		}
	}
	int res=0;
	for(int i=1;i<=n;++i)	res=max(res,f[i]);
	return res;
}
bool bfs()
{
	for(int i=s;i<=t;++i)	dep[i]=0;
	int nowl=1,nowr=1;
	ali[1]=s;
	dep[s]=1;
	while(nowl<=nowr)
	{
		int u=ali[nowl++];
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i],w=val[i];
			if(w&&!dep[v])
			{
				dep[v]=dep[u]+1;
				ali[++nowr]=v;
			}
		}
	}
	return dep[t];
}
int dfs(int u,int in)
{
	if(u==t)	return in;
	int out=0;
	for(int i=head[u];i;i=nxt[i])
	{
		if(!in)	break;
		int v=to[i],w=val[i];
		if(w&&dep[v]==dep[u]+1)
		{
			int ret=dfs(v,min(in,w));
			val[i]-=ret;
			val[i^1]+=ret;
			in-=ret;
			out+=ret;
		}
	}
	if(!out)	dep[u]=0;
	return out;
}
int dinic()
{
	int res=0;
	while(bfs())	res+=dfs(s,INF);
	return res;
}
int getans()
{
	cntot=1;
	for(int i=s;i<=t;++i)	head[i]=0;
	for(int i=1;i<=n;++i)
	{
		if(f[i]==1)	addedge(s,i,1);
		else if(f[i]==len)	addedge(i,t,1);
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<i;++j)
		{
			if(a[j]<=a[i]&&f[i]==f[j]+1)	addedge(j,i,1);
		}
	}
	return dinic();
}
int exgetans()
{
	cntot=1;
	for(int i=s;i<=t;++i)	head[i]=0;
	for(int i=1;i<=n;++i)
	{
		if(f[i]==1)
		{
			if(i==1||i==n)	addedge(s,i,INF);
			else	addedge(s,i,1);
		}
		else if(f[i]==len)
		{
			if(i==1||i==n)	addedge(i,t,INF);
			else	addedge(i,t,1);
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<i;++j)
		{
			if(a[j]<=a[i]&&f[i]==f[j]+1)	addedge(j,i,1);
		}
	}
	return dinic();
}
int main()
{
	scanf("%d",&n);
	s=0;
	t=n+1;
	for(int i=1;i<=n;++i)	scanf("%d",&a[i]);
	len=getstr();
	printf("%d\n",len);
	if(len>1)
	{
		printf("%d\n",getans());
		printf("%d\n",exgetans());
	}
	else	printf("%d\n%d\n",n,n);
	return 0;
}

∆ HDU4940 无源汇上下界可行流 / Destroy Transportation system - AC

流板。

#include <cstdio>
#include <cstring>

const int MAXN = 800 + 5, MAXM = 41000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Graph {
	int to, nx, wt;
	Graph () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	Graph ( const int a, const int b, const int c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[( MAXN + MAXM ) * 2];

struct Edge {
	int u, v, wtl, wtr;
	Edge () : u ( 0 ), v ( 0 ), wtl ( 0 ), wtr ( 0 ) {}
	Edge ( const int a, const int b, const int c, const int d ) : u ( a ), v ( b ), wtl ( c ), wtr ( d ) {}
} eds[MAXM];

int n, m, s, t, ups[MAXN], dns[MAXN], bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN], all, kase;

void addE ( const int u, const int v, const int w ) {
	as[++ cnt] = Graph ( v, bgn[u], w ), bgn[u] = cnt;
	as[++ cnt] = Graph ( u, bgn[v], 0 ), bgn[v] = cnt;
}

void clearIt () {
	cnt = 1;
	memset ( bgn, 0, sizeof ( bgn ) );
	memset ( ups, 0, sizeof ( ups ) );
	memset ( dns, 0, sizeof ( dns ) );
}

bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to, w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, int in ) {
	if ( u == t )	return in;
	int out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to, w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

int calcMXflow () {
	int res = 0;
	for ( ; bfs (); res += dfs ( s, 1e9 ) ) ;
	return res;
}

void solveIt () {
	n = rint (), m = rint (), s = 0, t = n + 1;
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint ();
		int lwr = rint (), upr = rint ();
		eds[i] = Edge ( u, v, lwr, lwr + upr );
	}
	for ( int i = 1; i <= m; ++ i ) {
		ups[eds[i].v] += eds[i].wtl;
		dns[eds[i].u] += eds[i].wtl;
		addE ( eds[i].u, eds[i].v, eds[i].wtr - eds[i].wtl );
	}
	for ( int i = 1; i <= n; ++ i ) {
		if ( ups[i] >= dns[i] )	addE ( s, i, ups[i] - dns[i] ), all += ups[i] - dns[i];
		else	addE ( i, t, dns[i] - ups[i] );
	}
	int ret = calcMXflow ();
	if ( ret == all )	printf ( "Case #%d: happy\n", ++ kase );
	else	printf ( "Case #%d: unhappy\n", ++ kase );
}

int main () {
	int dats = rint ();
	for ( ; dats; dats -- )	clearIt (), solveIt ();
	return 0;
}

∆ LOC8381 网络流 24题飞行员配对方案问题 - AC

流板。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 8e5 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx, wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const int c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXN * 2];

int m, n, s, t, out, eng, bgn[MAXN], cur[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void addE ( const int u, const int v, const int w ) {
	as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt;
	as[++ cnt] = GraphSet ( u, bgn[v], 0 ), bgn[v] = cnt;
}

bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0, cur[i] = bgn[i];
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to, w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

int dfs ( const int u, int in ) {
	if ( u == t )	return in;
	int out = 0;
	for ( int i = cur[u]; i; i = as[i].nx ) {
		cur[u] = i;
		if ( ! in )	break;
		int v = as[i].to, w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

int calcMXflow () {
	int res = 0;
	for ( ; bfs (); res += dfs ( s, INF ) ) ;
	return res;
}

int main () {
	m = rint (), n = rint (), out = m, eng = n - m;
	s = 1, t = out + eng + 2;
	for ( int i = 1; i <= out; ++ i )	addE ( s, i + 1, 1 );
	for ( ; ; ) {
		int u = rint (), v = rint ();
		if ( ~ u && ~ v )	addE ( u + 1, v + 1, 1 );
		else	break;
	}
	for ( int i = 1; i <= eng; ++ i )	addE ( i + out + 1, t, 1 );
	int ret = calcMXflow ();
	wint ( ret ), putchar ( '\n' );
	for ( int _ = 1; _ <= out; ++ _ ) {
		int u = _ + 1;
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to, w = as[i].wt;
			if ( v == 1 )	continue;
			if ( ! w ) {
				wint ( u - 1 ), putchar ( ' ' );
				wint ( v - 1 ), putchar ( '\n' );
				break;
			}
		}
	}
	return 0;
}

∆ ZOJ2314 / SGU194 无源汇上下界可行流 Reactor Cooling - AC

流板。

#include <cstdio>

typedef long long LL;

const LL INF = 1e18;
const int MAXN = 200 + 5, MAXM = 10200 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[( MAXN + MAXM ) * 2];

struct EdgeSet {
	int u, v;
	LL wtl, wtr;
	EdgeSet () : u ( 0 ), v ( 0 ), wtl ( 0 ), wtr ( 0 ) {}
	EdgeSet ( const int a, const int b, const LL c, const LL d ) : u ( a ), v ( b ), wtl ( c ), wtr ( d ) {}
} eds[MAXM];

int n, m, s, t, bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];
LL ups[MAXN], outs[MAXN], all;

void addE ( const int u, const int v, const LL w ) {
	as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt;
	as[++ cnt] = GraphSet ( u, bgn[v], 0 ), bgn[v] = cnt;
}

bool bfs () {
	for ( int i = s; i <= t; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, INF ) ) ;
	return res;
}

void solve () {
	n = rint (), m = rint (), s = 0, t = n + 1;
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint ();
		LL lower = rint (), upper = rint ();
		eds[i] = EdgeSet ( u, v, lower, upper );
	}
	for ( int i = 1; i <= m; ++ i )	ups[eds[i].v] += eds[i].wtl, outs[eds[i].u] += eds[i].wtl;
	for ( int i = 1; i <= m; ++ i )	addE ( eds[i].u, eds[i].v, eds[i].wtr - eds[i].wtl );
	for ( int i = 1; i <= n; ++ i ) {
		if ( ups[i] >= outs[i] )	addE ( s, i, ups[i] - outs[i] ), all += ups[i] - outs[i];
		else	addE ( i, t, outs[i] - ups[i] );
	}
	LL ret = calcMXflow ();
	if ( ret == all ) {
		puts ( "YES" );
		for ( int i = 2; i <= ( m << 1 | 1 ); i += 2 )	wint ( eds[i >> 1].wtl + as[i ^ 1].wt ), putchar ( '\n' );
	}
	else	puts ( "NO" );
}

#include <cstring>
void clearIt () {
	n = m = s = t = all = 0;
	cnt = 1;
	memset ( bgn, 0, sizeof ( bgn ) );
	memset ( lav, 0, sizeof ( lav ) );
	memset ( ali, 0, sizeof ( ali ) );
	memset ( ups, 0, sizeof ( ups ) );
	memset ( outs, 0, sizeof ( outs ) );
	memset ( eds, 0, sizeof ( eds ) );
	memset ( as, 0, sizeof ( as ) );
}

int main () {
	for ( int i = rint (); i; -- i )	clearIt (), solve ();
	return 0;
}

∆ LOC26241 开灯问题 - AC

记录 lft，ths，rgt 即可。

分别表示左边是否全亮，这里亮没，最右。

/* Clearink */

#include <cstdio>

namespace mySpace {
const int MAXN = 5e4 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }

int n, rgt, ths[MAXN], lft[MAXN], mdf[MAXN], ans;

void main () {
	n = rint ();
	for ( int i = 1; i <= n; ++ i )	mdf[i] = rint ();
	for ( int i = 1; i <= n; ++ i ) {
		ths[mdf[i]] = 1;
		rgt = MAX ( rgt, mdf[i] );
		if ( mdf[i] == 1 )	lft[mdf[i]] = 1;
		else {
			if ( lft[mdf[i] - 1] )	lft[mdf[i]] = 1;
		}
		if ( lft[mdf[i]] ) {
			for ( int j = mdf[i] + 1; j <= rgt; ++ j ) {
				if ( ths[j] )	lft[j] = 1;
				else	break;
			}
		}
		if ( lft[rgt] )	ans ++;
	}
	wint ( ans ), putchar ( '\n' );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ LOC11144 完美数 - AC

相当于让你构造出一个最小的数，使得该数的阶乘的因子有 $\prod a_{i}\times q$ 。

原题。

/* Clearink */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 1e5 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

int n, a[MAXN], psn[MAXN], psc, tg[MAXN], ar[MAXN], buc[MAXN];

void sieve ( const int li ) {
	for ( int i = 2; i <= li; ++ i ) {
		if ( ! tg[i] )	psn[++ psc] = ar[i] = i;
		for ( int j = 1; j <= psc && i * psn[j] <= li; ++ j ) {
			tg[i * psn[j]] = 1, ar[i * psn[j]] = psn[j];
			if ( i % psn[j] == 0 )	break;
		}
	}
}

bool chkok ( const int x ) {
	int tmp = 0;
	for ( int i = 1; i <= psc; ++ i ) {
		int bk = x;
		for ( ; bk; bk /= psn[i] )	tmp += bk / psn[i];
		if ( buc[psn[i]] > tmp )	return 0;
		tmp = 0;
	}
	return 1;
}

int brysrc ( const int pL, const int pR ) {
	int l = pL, r = pR, res = 0;
	for ( ; l <= r; ) {
		int mid = ( l + r ) >> 1;
		if ( chkok ( mid ) )	r = mid - 1, res = mid;
		else	l = mid + 1;
	}
	return res;
}

void main () {
	n = rint (), sieve ( 1e5 );
	for ( int i = 1, x; i <= n; ++ i ) {
		x = rint ();
		for ( ; x > 1; x /= ar[x] )	++ buc[ar[x]];
	}
	wint ( brysrc ( 1, 1e8 ) ), putchar ( '\n' );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ LOC11145 诗意狗 - AC

原题。

/* Clearink */

#include <cstdio>

namespace mySpace {
const int MAXN = 1e5 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

struct GraphSet {
	int to, nx;
	GraphSet () : to ( 0 ), nx ( 0 ) {}
	GraphSet ( const int a, const int b ) : to ( a ), nx ( b ) {}
} as[MAXN * 2];

int n, k, bgn[MAXN], cnt, ils;

void addE ( const int u, const int v ) { as[++ cnt] = GraphSet ( v, bgn[u] ), bgn[u] = cnt; }
void clearIt ( const int li ) { for ( int i = 1; i <= li; ++ i )	bgn[i] = 0; cnt = ils = 0; }

bool dfs ( const int u ) {
	bool res = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		int v = as[i].to;
		bool ret = dfs ( v );
		if ( ! res && ret )	++ ils, res = 1;
	}
	return res ^ 1;
}

void main () {
	for ( int datBas = rint (); datBas; datBas -- ) {
		n = rint (), k = rint (), clearIt ( n );
		for ( int i = 2, f; i <= n; ++ i )	f = rint (), addE ( f, i );
		bool waste = dfs ( 1 );
		if ( ( ils << 1 ) < k )	wint ( k - ils ), putchar ( '\n' );
		else	wint ( ( k >> 1 ) + ( k & 1 ) ), putchar ( '\n' );
	}
}
}
 
int main () {
	mySpace :: main ();
	return 0;
}

∆ LOC11146 山海 - AC

原题，但当时没做出来，现在来挑战一下。

设 $f_{i,j}$ 表示前 $i$ 个数的 prod 与 $k$ 的最大公约数为 $k$ 的第 $j$ 个约数的方案数。

则有方程：

f_{i,j}=\sum f_{i-1,p}\times f_{1,\lfloor\frac{j}{p}\rfloor},\texttt{p 代表 k 的第 p 个约数，j 同理。p[k]|p[j]}

不行，要死。

记 $k$ 的因数为 $psk_{i}$ 。

考虑预处理出 $f_{1,i}$ ，也就是求满足 $x\in[1,m],\gcd(x,k)=psk_{i}$ 的 $x$ 的数量。

由推 Mobius Inversion 式子时的常用套路可转化为 $x\in[1,\lfloor\frac{m}{psk_{i}}\rfloor],\gcd(x,k)=1$ 的 $x$ 的数量。

为方便，记 $l=\lfloor\frac{m}{psk_{i}}\rfloor$ 。

现在我们要找的是 $[1,l]$ 中没有 $psk_{i}$ 约数的数的个数，我们知道 $\lfloor\frac{x}{y}\rfloor$ 表示的是 $[1,x]$ 中有约数 $y$ 的数的个数。

然后我们就可以容斥了，搜索即可。

/* Clearink */

#include <cstdio>
#include <algorithm>

using namespace std;

namespace mySpace {
#define mod ( 10007 )

const int MAXN = 4e3 + 5, MAXM = 1e5 + 5, MAXK = 1e7 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

int n, m, k, psk[MAXM], skn, psp[MAXM], spn, f[MAXN][MAXN], cur, inv[MAXK], upper, bid[MAXN][MAXN], siz[MAXN];

void divide1 ( int val ) {
	for ( int i = 2; i * i <= val; ++ i ) {
		if ( val % i == 0 ) {
			psp[++ spn] = i;
			for ( ; val % i == 0; val /= i ) ;
		}
		if ( val == 1 )	break;
	}
	if ( val > 1 )	psp[++ spn] = val;
	sort ( psp + 1, psp + 1 + spn );
}

void divide2 ( int val ) {
	for ( int i = 1; i * i <= val; ++ i ) {
		if ( k % i == 0 ) {
			psk[++ skn] = i;
			if ( i * i != val )	psk[++ skn] = val / i;
		}
	}
	sort ( psk + 1, psk + 1 + skn );
}

void dfs ( const int a, const int b, const int c ) {
	if ( a > spn )	return void ( cur += upper / c * b );
	dfs ( a + 1, b, c ), dfs ( a + 1, -b, c * psp[a] );
}

void main () {
	n = rint (), m = rint (), k = rint ();
	divide1 ( k ), divide2 ( k );
	for ( int i = 1; i <= skn; ++ i ) {
		inv[psk[i]] = i, cur = 0, upper = m / psk[i];
		dfs ( 1, 1, 1 ), f[1][i] = cur % mod;
	}
	for ( int i = 1; i <= skn; ++ i ) {
		for ( int j = 1; j <= i; ++ j ) {
			if ( psk[i] % psk[j] == 0 )	bid[i][++ siz[i]] = j;
		}
	}
    for ( int i = 2; i <= n; ++ i ) {
    	for ( int j = 1; j <= skn; ++ j ) {
    		if ( ! siz[j] )	continue;
    		for ( int p = 1; p <= siz[j]; ++ p )
				f[i][j] = ( f[i][j] + f[i - 1][bid[j][p]] * f[1][inv[psk[j] / psk[bid[j][p]]]] ) % mod;
		}
	}
	wint ( f[n][skn] ), putchar ( '\n' );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ LOJ6197 法克 - AC

题意：给出一个 DAG，求最多选出几个点使得互相不可达。

相当于就是选出那么多条链使得他们的点集的交集为空。然后不会了。

看了看题解发现要用一个定理，名字好像叫 Dilworth Theorem。

Dilworth Theorem：

最长反链长度=最小链覆盖（用最少的链覆盖所有顶点）
最长链长度=最小反链覆盖（用最少的反链覆盖所有顶点）

反链：任意两点没有路径的点集。

那么我们把问题扯成了求 DAG 的最小链覆盖，具体可看这篇。

但是他的方法过于暴力，过不了题。

优化就用网络流，连边 $c(s,i)=1,c(i+n,t)=1,c(a,b+n)=\infty,c(i+n,i)=\infty$ 。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 8e5 + 5, MAXM = MAXN * 2;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXN * 2];

int q[MAXN];
int n, m, head[MAXN], ecnt = 1, lav[MAXN], npts, cur[MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, q[++ t] = v;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		int ret = dfs ( v, aim, MIN ( flow - used, w ) );
		graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
		if ( flow == used )	break;
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= npts; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (), npts = 2 * n;
	const int supS = ++ npts, supT = ++ npts;
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint ();
		link ( u, v + n, INF );
	}
	for ( int i = 1; i <= n; ++ i )	link ( supS, i, 1 ), link ( i + n, supT, 1 ), link ( i + n, i, INF );
	printf ( "%d\n", n - calcMXflow ( supS, supT ) );
	return 0;
}

∆ ZOJ2676 网络战争 - AC

二分答案。

#include <cstdio>

const double INF = 1e18, EPS = 1e-8;
const int MAXN = 1e2 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T ABS ( const _T x ) { return x < 0 ? -x : x; }
template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }
template<typename _T> bool EQ ( const _T x, const _T y ) { return ABS ( x - y ) < EPS; }

struct Edge { int to, nxt; double cst; } graph[MAXM * 2], as[MAXM];

int q[MAXN];
int n, m, head[MAXN], ecnt = 1, lav[MAXN], npts, cur[MAXN];

void link ( const int u, const int v, const double w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 
		w }, head[v] = ecnt;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to; double w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

double dfs ( const int u, const int aim, double flow ) {
	if ( u == aim )	return flow;
	double used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to; double w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			double ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( EQ ( flow, used ) )	break;
		}
	}
	if ( used < flow )	lav[u] = 0;
	return used;
}

double calcMXflow ( const int supS, const int supT ) {
	double res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= npts; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

bool check ( const double x, const int supS, const int supT ) {
	ecnt = 1;
	for ( int i = 1; i <= npts; ++ i )	head[i] = 0;
	double negx = 0;
	for ( int i = 1; i <= m; ++ i ) {
		if ( as[i].cst - x < 0 || EQ ( as[i].cst - x, 0.0 ) )	negx += as[i].cst - x;
		else	link ( as[i].to, as[i].nxt, as[i].cst - x );
	}
	double ret = calcMXflow ( supS, supT );
	return ret + negx < 0 || EQ ( ret + negx, 0.0 );
}

int main () {
	n = npts = rint (), m = rint ();
	const int supS = rint (), supT = rint ();
	for ( int i = 1; i <= m; ++ i )	as[i] = { rint (), rint (), ( double )rint () };
	double l = 0, r = 1e18, ans = 0;
	for ( int i = 1; i <= 100; ++ i ) {
		double mid = ( l + r ) / 2;
		if ( check ( mid, supS, supT ) )	r = mid, ans = mid;
		else	l = mid;
	}
	printf ( "%.2lf\n", ans );
	return 0;
}

∆ LOC5125 网络流 24 题方格取数 - AC

像某道迭代加深的题一样，我们可以反过来考虑这个问题。

然后肆意连边。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 4e4 + 5, MAXM = MAXN * 8;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int q[MAXN];
int n, m, head[MAXN], ecnt = 1, lav[MAXN], npts, cur[MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int hs ( const int x, const int y ) { return ( x - 1 ) * m + y; }
bool is ( const int x, const int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( used < flow )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= npts; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (), npts = n * m;
	int sum = 0;
	const int supS = ++ npts, supT = ++ npts;
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			int x = rint (); sum += x;
			if ( ( i + j ) & 1 )	link ( supS, hs ( i, j ), x );
			else	link ( hs ( i, j ), supT, x );
		}
	}
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			if ( ( i + j ) & 1 ) {
				if ( is ( i - 1, j ) )	link ( hs ( i, j ), hs ( i - 1, j ), INF );
				if ( is ( i + 1, j ) )	link ( hs ( i, j ), hs ( i + 1, j ), INF );
				if ( is ( i, j - 1 ) )	link ( hs ( i, j ), hs ( i, j - 1 ), INF );
				if ( is ( i, j + 1 ) )	link ( hs ( i, j ), hs ( i, j + 1 ), INF );
			}
		}
	}
	printf ( "%d\n", sum - calcMXflow ( supS, supT ) );
	return 0;
}

∆ LOC5151 百步穿杨 - AC

称箭塔为 ST，箭靶为 BST。

拆点，把每一个 BST 拆成 $o$ 和 $o'$ ，反之亦然。

贪个心，每一个 ST 取自己领空中最大的。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 2e6 + 5, MAXS = 1e3 + 5;

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }
template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }

int q[MAXN]; char s[MAXS][MAXS];
int n, m, head[MAXN], ecnt = 1, cur[MAXN], lav[MAXN], npts;

struct Edge { int to, nxt, cst; } graph[MAXM * 2];
struct Point { int x, y; } ;

int hs ( const int x, const int y ) { return ( x - 1 ) * m + y; }
bool isb ( const char x ) { return x - '0' >= 1 && x - '0' <= 9; }
bool isd ( const int x, const int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }
bool isd ( const Point x ) { return isd ( x.x, x.y ); }

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int trans ( const char x ) {
	switch ( x ) {
		case 'A': return 0; break;
		case 'V': return 1; break;
		case '<': return 2; break;
		case '>': return 3; break;
	}
	return -1;
}

Point getCHed ( int& x, int& y, const char d ) {
	switch ( trans ( d ) ) {
		case 0: x --; break;
		case 1: x ++; break;
		case 2: y --; break;
		case 3: y ++; break;
	}
	return { x, y };
}

int findMXpath ( const int x, const int y, const char d ) {
	int res = 0;
	int nowx = x, nowy = y;
	for ( ; isd ( nowx, nowy ); getCHed ( nowx, nowy, d ) ) {
		if ( isb ( s[nowx][nowy] ) )	res = MAX ( res, s[nowx][nowy] - '0' );
	}
	return res;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= npts; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	scanf ( "%d%d", &n, &m ), npts = n * m * 2;
	const int supS = ++ npts, supT = ++ npts;
	int all = 0;
	for ( int i = 1; i <= n; ++ i )	scanf ( "%s", s[i] + 1 );
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			link ( hs ( i, j ), hs ( i, j ) + n * m, INF );
			const auto& rep = s[i][j];
			if ( ~ trans ( rep ) ) {
				if ( trans ( rep ) < 2 )	link ( supS, hs ( i, j ), INF );
				else	link ( hs ( i, j ) + n * m, supT, INF );
				int x = i, y = j, tmp;
				all += ( tmp = findMXpath ( i, j, rep ) ), getCHed ( x, y, rep );
				if ( isd ( x, y ) ) {
					if ( trans ( rep ) < 2 )	link ( hs ( i, j ), hs ( x, y ), tmp );
					else	link ( hs ( x, y ) + n * m, hs ( i, j ), tmp );
					Point tpo = { x, y }; getCHed ( tpo.x, tpo.y, rep );
					for ( ; isd ( tpo ); getCHed ( x, y, rep ) ) {
						int c = tmp, tx = x, ty = y; getCHed ( tx, ty, rep );
						if ( isb ( s[x][y] ) )	c -= s[x][y] - '0';
						if ( trans ( rep ) < 2 )	link ( hs ( x, y ), hs ( tx, ty ), c );
						else	link ( hs ( tx, ty ) + n * m, hs ( x, y ) + n * m, c );	
						getCHed ( tpo.x, tpo.y, rep );
					}
				}
			}
		}
	}
	printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ P4174 [NOI2006]最大获利 - AC

...

#include<cstdio>
#include<queue>
using namespace std;
const int INF=1e9;
queue<int> que;
int n,m,head[20010],cntot=1,lav[20010],cur[20010],nxt[800010],to[800010],val[800010],npts,pnt[20010],p[20010],all;
int rint()
{
	int x=0,f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar())	f=c=='-'?-1:f;
	for(;c>='0'&&c<='9';c=getchar())	x=(x<<3)+(x<<1)+(c&15);
	return x*f;
}
void link(int u,int v,int w)
{
	to[++cntot]=v;
	nxt[cntot]=head[u];
	val[cntot]=w;
	head[u]=cntot;
	to[++cntot]=u;
	nxt[cntot]=head[v];
	val[cntot]=0;
	head[v]=cntot;
}
bool bfs(int supS,int supT)
{
	while(!que.empty())	que.pop();
	for(int i=1;i<=npts;++i)	lav[i]=0;
	que.push(supS);
	lav[supS]=1;
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i],w=val[i];
			if(w&&!lav[v])
			{
				que.push(v);
				lav[v]=lav[u]+1;
			}
		}
	}
	return lav[supT];
}
int dfs(int u,int aim,int flow)
{
	if(u==aim)	return flow;
	int used=0;
	for(int& i=cur[u];i;i=nxt[i])
	{
		int v=to[i],w=val[i];
		if(w&&lav[v]==lav[u]+1)
		{
			int ret=dfs(v,aim,min(flow-used,w));
			val[i]-=ret;
			val[i^1]+=ret;
			used+=ret;
			if(flow==used)	break;
		}
	}
	if(!used)	lav[u]=0;
	return used;
}
int dinic(int supS,int supT)
{
	int res=0;
	while(bfs(supS,supT))
	{
		for(int i=1;i<=npts;++i)	cur[i]=head[i];
		res+=dfs(supS,supT,INF);
	}
	return res;
}
int main()
{
	npts=n=rint();
	m=rint();
	const int supS=++npts,supT=++npts;
	for(int i=1;i<=n;++i)	p[i]=rint();
	for(int i=1;i<=m;++i)
	{
		int u=rint(),v=rint(),w=rint();
		pnt[u]+=w;
		pnt[v]+=w;
		link(u,v,w);
		link(v,u,w);
	}
	for(int i=1;i<=n;++i)
	{
		if(pnt[i]-(p[i]<<1)>=0)
		{
			link(supS,i,pnt[i]-(p[i]<<1));
			all+=pnt[i]-(p[i]<<1);
		}
		else	link(i,supT,(p[i]<<1)-pnt[i]);
	}
	printf("%d\n",(all-dinic(supS,supT))>>1);
	return 0;
}

∆ LOC3094 网络流 24 题太空飞行计划问题

。。。

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=1e9;
const int MAXN=200+5,MAXM=MAXN*MAXN*10;
queue<int> que;
int expnu,insnu,head[MAXN],cntot=1,nxt[MAXM],to[MAXM],val[MAXM],lav[MAXN],p[MAXN],w[MAXN],all,vis[MAXN],cur[MAXN];
char tools[10000];
vector<int> R[MAXN],exps,inss;
void link(int one,int ano,int cst)
{
	to[++cntot]=ano;
	nxt[cntot]=head[one];
	val[cntot]=cst;
	head[one]=cntot;
	to[++cntot]=one;
	nxt[cntot]=head[ano];
	val[cntot]=0;
	head[ano]=cntot;
}
bool bfs(int supS,int supT)
{
	for(int i=supS;i<=supT;++i)	lav[i]=0;
	que.push(supS);
	lav[supS]=1;
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i],c=val[i];
			if(c&&!lav[v])
			{
				lav[v]=lav[u]+1;
				que.push(v);
			}
		}
	}
	return lav[supT];
}
int dfs(int u,int aim,int flow)
{
	if(u==aim)	return flow;
	int used=0;
	for(int& i=cur[u];i;i=nxt[i])
	{
		int v=to[i],c=val[i];
		if(c&&lav[v]==lav[u]+1)
		{
			int ret=dfs(v,aim,min(flow-used,c));
			val[i]-=ret;
			val[i^1]+=ret;
			used+=ret;
			if(flow==used)	break;
		}
	}
	if(used<flow)	lav[u]=0;
	return used;
}
int dinic(int supS,int supT)
{
	int res=0;
	while(bfs(supS,supT))
	{
		for(int i=supS;i<=supT;++i)	cur[i]=head[i];
		res+=dfs(supS,supT,INF);
	}
	return res;
}
void exdfs(int u)
{
	if(vis[u])	return;
	vis[u]=1;
	if(u>0)
	{
		if(u<=insnu)	inss.push_back(u);
		else	exps.push_back(u-insnu);
	}
	for(int i=head[u];i;i=nxt[i])
	{
		if(val[i])	exdfs(to[i]);
	}
}
int main()
{
	scanf("%d%d",&expnu,&insnu);
	const int supS=0,supT=expnu+insnu+1;
	for(int i=1;i<=expnu;++i)
	{
		scanf("%d",&p[i]);
		memset(tools,0,sizeof tools);
		cin.getline(tools,10000);
		int ulen=0,tool;
		while(sscanf(tools+ulen,"%d",&tool)==1)
		{
		    R[i].push_back(tool);
			if(tool==0)	ulen++;
		    else
			{
		        while(tool)
				{
		            tool/=10;
		            ulen++;
		        }
		    }
		    ulen++;
		}
	}
	for(int i=1;i<=insnu;++i)	scanf("%d",&w[i]);
	for(int i=1;i<=expnu;++i)
	{
		all+=p[i];
		link(supS,i+insnu,p[i]);
		for(int x:R[i])	link(i+insnu,x,INF);
	}
	for(int i=1;i<=insnu;++i)	link(i,supT,w[i]);
	all-=dinic(supS,supT);
	exdfs(supS);
	for(int i:exps)	printf("%d ",i);
	puts("");
	for(int i:inss)	printf("%d ",i);
	puts("");
	printf("%d\n",all);
	return 0;
}

∆ UVA1389 Hard Life - AC

傻逼 / 死妈 / fuckyoumotherfuckerbitchifuckingscrewyourwholefamilygofuckyourselfandyourfamily 的特判。

#include <cstdio>
#include <queue>
#include <cstring>

const double INF = 1e4, EPS = 1e-7;
const int MAXN = 2e3 + 5, MAXM = 5e3 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () ) {
		if ( ~ c )	f = c == '-' ? -1 : f;
		else	return EOF;
	}
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T ABS ( const _T x ) { return x < 0 ? -x : x; }
template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }
template<typename _T> bool EQ ( const _T x, const _T y = 0 ) { return ABS ( x - y ) <= EPS; }

struct Edge { int to, nxt; double cst; } graph[MAXM * 2];
struct rEdge { int u, v; } as[MAXM];

int q[MAXN];
int n, m, head[MAXN], ecnt = 1, lav[MAXN], npts, cur[MAXN], vis[MAXN];

void link ( const int u, const int v, const double w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= npts; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to; double w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

double dfs ( const int u, const int aim, double flow ) {
	if ( u == aim )	return flow;
	double used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to; double w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			double ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( used < flow )	lav[u] = 0;
	return used;
}

double calcMXflow ( const int supS, const int supT ) {
	double res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= npts; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

void connectEdges ( const double lyc, const int supS, const int supT ) {
	for ( int i = 1; i <= m; ++ i )	link ( supS, i + n, 1 );
	for ( int i = 1; i <= n; ++ i )	link ( i, supT, lyc );
	for ( int i = 1; i <= m; ++ i )	link ( i + n, as[i].u, INF ), link ( i + n, as[i].v, INF );
}

bool check ( const double x, const int supS, const int supT ) {
	ecnt = 1;
	for ( int i = 1; i <= npts; ++ i )	head[i] = 0;
	connectEdges ( x, supS, supT );
	return m - calcMXflow ( supS, supT ) > EPS;
}

double search ( double l, double r, const int supS, const int supT ) {
	double res = 0;
	for ( int i = 1; i <= 60; ++ i ) {
		double mid = ( l + r ) / 2;
		if ( ! check ( mid, supS, supT ) )	r = mid;
		else	l = mid, res = mid;
	}
	return res;
}

void path ( const int u ) {
	vis[u] = 1;
	for ( int i = head[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to; double w = graph[i].cst;
		if ( w && ! vis[v] )	path ( v );
	}
}

int main () {
	while ( ~ ( n = rint () ) && ~ ( m = rint () ) ) {
		if ( ! m )	printf ( "1\n1\n" );
		for ( int i = 1; i <= npts; ++ i )	vis[i] = 0;
		npts = n + m, ecnt = 1;
		const int supS = ++ npts, supT = ++ npts;
		for ( int i = 1; i <= m; ++ i )	as[i] = { rint (), rint () };
		double ret = search ( 0, m, supS, supT );
		for ( int i = 1; i <= npts; ++ i )	head[i] = 0; ecnt = 1;
		connectEdges ( ret, supS, supT ), calcMXflow ( supS, supT );
		path ( supS ); int ans = 0;
		for ( int i = 1; i <= n; ++ i )	ans += vis[i];
		printf ( "%d\n", ans );
		for ( int i = 1; i <= n; ++ i ) {
			if ( vis[i] )	printf ( "%d\n", i );
		}
	}
	return 0;
}

∆ P3749 [六省联考2017]寿司餐厅 - AC

wow.

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e6 + 5, MAXM = 1e6 + 10;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }
template<typename _T> _T MAX ( const _T x, const _T y ) { return x < y ? y : x; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXN], ecnt = 1, lav[MAXN], q[MAXN], ID[MAXN], ntot, cur[MAXN], all;

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int trans ( const int x, const int y ) { return ( x - 1 ) * n + y; }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= ntot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= ntot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (); int upper = 0; ntot = n * n + m;
	for ( int i = 1; i <= n; ++ i )	ID[i] = rint (), upper = MAX ( upper, ID[i] );
	ntot += upper - 1; const int supS = ++ ntot, supT = ++ ntot;
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = i; j <= n; ++ j ) {
			int c = rint ();
			if ( i == j )	link ( trans ( i, j ), n * n + ID[i], INF ), c -= ID[i];
			else	link ( trans ( i, j ), trans ( i, j - 1 ), INF ), link ( trans ( i, j ), trans ( i + 1, j ), INF );
			if ( c > 0 )	link ( supS, trans ( i, j ), c ), all += c;
			else	link ( trans ( i, j ), supT, -c );
		}
	}
	for ( int i = 1; i <= upper; ++ i )	link ( n * n + i, supT, i * i * m );
	printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ P4177 [CEOI2008]order - AC

qwq.

#include <cstdio>

const int INF = 1e9;
const int MAXN = 2e5 + 5, MAXM = 2e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXN], ecnt = 1, cur[MAXN], lav[MAXN], q[MAXN], ntot, all;

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= ntot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int flow, const int aim ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, MIN ( flow - used, w ), aim );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= ntot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, INF, supT );
	}
	return res;
}

int main () {
	n = rint (), m = rint (); ntot = n + m;
	const int supS = ++ ntot, supT = ++ ntot;
	for ( int i = 1; i <= n; ++ i ) {
		int p = rint (), t = rint ();
		all += p, link ( supS, i, p );
		while ( t -- > 0 ) {
			int ID = rint (), cs = rint ();
			link ( i, ID + n, cs );
		}
	}
	for ( int i = 1; i <= m; ++ i )	link ( i + n, supT, rint () );
	printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ P3702 [SDOI2017]序列计数 - AC

一个复杂度 $O(p^{2}\log_{2}n+m)$ 的 rubbish 做法。

首先肯定把答案序列放在模 $p$ 意义下。

然后给出原问题的生成函数： $G(x)$ 的 $x^{i}$ 系数为 $n=1$ 时 $\bmod p=i$ 的答案，然后 $G^{n}(x)$ 就为答案的生成函数了。

由于这题的 $p$ 小飞了所以直接暴力乘法即可连 NTT 都不用……

#include <cstdio>
#include <cstring>
#define mod ( 20170408 )

typedef long long LL;

const int MAXM = 2e7 + 5, MAXP = 100 + 5;

int add ( const int a, const int b, const int p ) { return a + b < p ? a + b : a + b - p; }
int sub ( const int a, const int b, const int p ) { return a - b < 0 ? a - b + p : a - b; }
int mul ( const LL a, const LL b, const int p ) { return a * b % p; }

struct Poly { int as[MAXP]; Poly () { memset ( as, 0, sizeof ( as ) ); } } ar, ia;

int n, m, p;
bool tag[MAXM];

Poly times ( const Poly a, const Poly b ) {
	Poly ret;
	for ( int i = 0; i < p; ++ i ) {
		for ( int j = 0; j < p; ++ j )	ret.as[(i + j) % p] = add ( ret.as[(i + j) % p], mul ( a.as[i], b.as[j], mod ), mod );
	}
	return ret;
}

void sieve ( const int L ) {
	static int pSet[MAXM], psc;
	tag[1] = 1;
	for ( int i = 2; i <= L; ++ i ) {
		if ( ! tag[i] )	pSet[++ psc] = i;
		for ( int j = 1; j <= psc && ( LL )i * pSet[j] <= L; ++ j ) {
			tag[i * pSet[j]] = 1;
			if ( i % pSet[j] == 0 )	break;
		}
	}
}

Poly cpow ( Poly bas, int idx ) {
	Poly res = bas;
	while ( idx ) {
		if ( idx & 1 )	res = times ( res, bas );
		if ( idx >>= 1 )	bas = times ( bas, bas );
	}
	return res;
}

int main () {
	scanf ( "%d%d%d", &n, &m, &p ), sieve ( m );
	for ( int i = 1; i <= m; ++ i ) {
		ar.as[i % p] ++;
		if ( tag[i] )	ia.as[i % p] ++;
	}
	printf ( "%d\n", sub ( cpow ( ar, n - 1 ).as[0], cpow ( ia, n - 1 ).as[0], mod ) );
	return 0;
}

∆ P2598 [ZJOI2009]狼和羊的故事 - AC

狼向源点连 $\infty$ 的边，羊向汇点连 $\infty$ 的边，每格向周围连边，最小割即答案。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXN], ecnt = 1, lav[MAXN], q[MAXN], cur[MAXN], ntot;

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int insid ( const int x, const int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }
int trans ( const int x, const int y ) { return ( x - 1 ) * m + y; }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= ntot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= ntot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (); ntot = n * m;
	const int supS = ++ ntot, supT = ++ ntot;
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			int x = rint ();
			if ( x == 1 )	link ( supS, trans ( i, j ), INF );
			else if ( x == 2 )	link ( trans ( i, j ), supT, INF );
			if ( insid ( i + 1, j ) )	link ( trans ( i, j ), trans ( i + 1, j ), 1 );
			if ( insid ( i, j + 1 ) )	link ( trans ( i, j ), trans ( i, j + 1 ), 1 );
			if ( insid ( i - 1, j ) )	link ( trans ( i, j ), trans ( i - 1, j ), 1 );
			if ( insid ( i, j - 1 ) )	link ( trans ( i, j ), trans ( i, j - 1 ), 1 );
		}
	}
	printf ( "%d\n", calcMXflow ( supS, supT ) );
	return 0;
}

∆ P1935 [国家集训队]圈地计划 - AC

这里是一个拆点做法。

首先染色。

把一个点拆成两个，连 $c(S,(i,j))=a_{i,j},c((i,j)',T)=b_{i,j},c((i,j),(i,j)')=\infty$ 。

但是这样的话可能出现两个都不选的情况。

也不是不可以解决，把连向起点和终点的边都加上一个极大的数，这样可以跑了（这里参考了 Tweetuzki 的做法）。

为什么这样是对的呢？因为我们求最小割的时候，中间 $((i,j),(i,j)')$ 的边是一定不会被割掉的。

这样的建出来的图（或许）很高效。

#include <cstdio>

const int INF = 1e9, HIG = 1e5;
const int MAXN = 1e3 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], ntot, all;
int coeA[MAXN][MAXN], coeB[MAXN][MAXN], coeC[MAXN][MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int insid ( const int x, const int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }
int trans ( const int x, const int y ) { return ( x - 1 ) * m + y; }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= ntot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= ntot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

void build ( const int supS, const int supT ) {
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			all += coeA[i][j] + coeB[i][j] + HIG;
			if ( ( i + j ) & 1 ) {
				link ( supS, trans ( i, j ), coeA[i][j] + HIG );
				link ( trans ( i, j ) + n * m, supT, coeB[i][j] + HIG );
				link ( trans ( i, j ), trans ( i, j ) + n * m, INF );
				if ( insid ( i + 1, j ) )	link ( trans ( i, j ), trans ( i + 1, j ), coeC[i][j] + coeC[i + 1][j] ), all += coeC[i][j];
				if ( insid ( i, j + 1 ) )	link ( trans ( i, j ), trans ( i, j + 1 ), coeC[i][j] + coeC[i][j + 1] ), all += coeC[i][j];
				if ( insid ( i - 1, j ) )	link ( trans ( i, j ), trans ( i - 1, j ), coeC[i][j] + coeC[i - 1][j] ), all += coeC[i][j];
				if ( insid ( i, j - 1 ) )	link ( trans ( i, j ), trans ( i, j - 1 ), coeC[i][j] + coeC[i][j - 1] ), all += coeC[i][j];
			}
			else {
				link ( supS, trans ( i, j ) + n * m, coeB[i][j] + HIG );
				link ( trans ( i, j ), supT, coeA[i][j] + HIG );
				link ( trans ( i, j ) + n * m, trans ( i, j ), INF );
				if ( insid ( i + 1, j ) )	link ( trans ( i, j ) + n * m, trans ( i + 1, j ) + n * m, coeC[i][j] + coeC[i + 1][j] ), all += coeC[i][j];
				if ( insid ( i, j + 1 ) )	link ( trans ( i, j ) + n * m, trans ( i, j + 1 ) + n * m, coeC[i][j] + coeC[i][j + 1] ), all += coeC[i][j];
				if ( insid ( i - 1, j ) )	link ( trans ( i, j ) + n * m, trans ( i - 1, j ) + n * m, coeC[i][j] + coeC[i - 1][j] ), all += coeC[i][j];
				if ( insid ( i, j - 1 ) )	link ( trans ( i, j ) + n * m, trans ( i, j - 1 ) + n * m, coeC[i][j] + coeC[i][j - 1] ), all += coeC[i][j];
			}
		}
	}
}

int main () {
	n = rint (), m = rint (); ntot = n * m * 2;
	const int supS = ++ ntot, supT = ++ ntot;
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j )	coeA[i][j] = rint ();
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j )	coeB[i][j] = rint ();
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j )	coeC[i][j] = rint ();
	build ( supS, supT ), printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ P4313 文理分科 - AC

略。

#include <cstdio>

const int INF = 1e9, HIG = 1e5;
const int MAXN = 1e3 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T ABS ( const _T x ) { return x < 0 ? -x : x; }
template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], ntot, all;
int ar[MAXN][MAXN], sc[MAXN][MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int insid ( const int x, const int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }
int trans ( const int x, const int y ) { return ( x - 1 ) * m + y; }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= ntot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= ntot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (); ntot = n * m * 3;
	const int supS = ++ ntot, supT = ++ ntot;
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j)	ar[i][j] = rint ();
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j)	sc[i][j] = rint ();
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			int exar = rint (); all += exar;
			link ( supS, trans ( i, j ) + n * m, exar );
			link ( trans ( i, j ) + n * m, trans ( i, j ), INF );
			if ( insid ( i + 1, j ) )	link ( trans ( i, j ) + n * m, trans ( i + 1, j ), INF );
			if ( insid ( i, j + 1 ) )	link ( trans ( i, j ) + n * m, trans ( i, j + 1 ), INF );
			if ( insid ( i - 1, j ) )	link ( trans ( i, j ) + n * m, trans ( i - 1, j ), INF );
			if ( insid ( i, j - 1 ) )	link ( trans ( i, j ) + n * m, trans ( i, j - 1 ), INF );
		}
	}
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			int exsc = rint (); all += exsc;
			link ( trans ( i, j ) + n * m * 2, supT, exsc );
			link ( trans ( i, j ), trans ( i, j ) + n * m * 2, INF );
			if ( insid ( i + 1, j ) )	link ( trans ( i + 1, j ), trans ( i, j ) + n * m * 2, INF );
			if ( insid ( i, j + 1 ) )	link ( trans ( i, j + 1 ), trans ( i, j ) + n * m * 2, INF );
			if ( insid ( i - 1, j ) )	link ( trans ( i - 1, j ), trans ( i, j ) + n * m * 2, INF );
			if ( insid ( i, j - 1 ) )	link ( trans ( i, j - 1 ), trans ( i, j ) + n * m * 2, INF );
		}
	}
	for ( int i = 1; i <= n; ++ i ) {
		for ( int j = 1; j <= m; ++ j ) {
			int cur = ar[i][j] - sc[i][j];
			if ( cur > 0 )	link ( supS, trans ( i, j ), cur ), all += ar[i][j];
			else	link ( trans ( i, j ), supT, -cur ), all += sc[i][j];
		}
	}
	printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ P1361 小M的作物 - AC

略

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T ABS ( const _T x ) { return x < 0 ? -x : x; }
template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], ntot, all;
int coeA[MAXN], coeB[MAXN];

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= ntot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= ntot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint ();
	for ( int i = 1; i <= n; ++ i )	coeA[i] = rint ();
	for ( int i = 1; i <= n; ++ i )	 coeB[i] = rint ();
	m = rint (); ntot = n + 2 * m;
	const int supS = ++ ntot, supT = ++ ntot;
	for ( int i = 1; i <= m; ++ i ) {
		int t = rint (), c1 = rint (), c2 = rint ();
		all += c1 + c2;
		link ( supS, i + n, c1 ), link ( i + n + m, supT, c2 );
		while ( t -- ) {
			int x = rint ();
			link ( i + n, x, INF );
			link ( x, i + n + m, INF );
		}
	}
	for ( int i = 1; i <= n; ++ i ) {
		int cur = coeA[i] - coeB[i];
		if ( cur > 0 )	link ( supS, i, cur ), all += coeA[i];
		else	link ( i, supT, -cur ), all += coeB[i];
	}
	printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ P4210 土地划分 - AC

(s,i,va_{i}),(i,t,vb_{i}),(u,v,\frac{ea_{(u,v)}+eb_{(u,v)}}{2}+ec_{u,v}) \\ (s,u,\frac{ea}{2}),(s,v,\frac{ea}{2}),(.....)

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], tot, all;

void link ( const int u, const int v, const int w, const int exw ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], exw }, head[v] = ecnt;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= tot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= tot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (); tot = n;
	const int supS = ++ tot, supT = ++ tot;
	link ( supS, 1, INF, 0 ), link ( n, supT, INF, 0 );
	for ( int i = 2; i < n; ++ i ) {
		int pA = rint () * 2; all += pA;
		link ( supS, i, pA, 0 );
	}
	for ( int i = 2; i < n; ++ i ) {
		int pB = rint () * 2; all += pB;
		link ( i, supT, pB, 0 );
	}
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint ();
		int eA = rint () * 2, eB = rint () * 2, eC = rint () * 2;
		all += eA + eB;
		link ( u, v, ( eA + eB ) / 2 + eC, ( eA + eB ) / 2 + eC );
		link ( supS, u, eA / 2, 0 ), link ( supS, v, eA / 2, 0 );
		link ( u, supT, eB / 2, 0 ), link ( v, supT, eB / 2, 0 );
	}
	printf ( "%d\n", ( all - calcMXflow ( supS, supT ) ) / 2 );
	return 0;
}

∆ P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查 - AC

\text{if will[i]=0}:(s,i,1) \\ \text{otherwise}:(i,t,1) \\ (u,v,1)

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], tot;

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], w }, head[v] = ecnt;
}

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= tot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= tot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (); tot = n;
	const int supS = ++ tot, supT = ++ tot;
	for ( int i = 1; i <= n; ++ i ) {
		int s = rint ();
		if ( ! s )	link ( supS, i, 1 );
		else	link ( i, supT, 1 );
	}
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint ();
		link ( u, v, 1 );
	}
	printf ( "%d\n", calcMXflow ( supS, supT ) );
	return 0;
}

∆ P1646 [国家集训队]happiness - AC

和这题基本差不多，不过我特么不拆点了。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], tot, all;
int idx;

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int insid ( const int x, const int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }
int trans ( const int x, const int y ) { return ( x - 1 ) * m + y; }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= tot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= tot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (), m = rint (); tot = ( 5 * m - 2 ) * n - 2 * m; int coe;
	const int supS = ++ tot, supT = ++ tot; idx = n * m;
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j )	all += ( coe = rint () ), link ( supS, trans ( i, j ), coe );
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j )	all += ( coe = rint () ), link ( trans ( i, j ), supT, coe );
	for ( int i = 1; i < n; ++ i )  for ( int j = 1; j <= m; ++ j ) {
		coe = rint (); all += coe;
		link ( supS, ++ idx, coe );
		link ( idx, trans ( i, j ), INF );
		link ( idx, trans ( i + 1, j ), INF );
	}
	for ( int i = 1; i < n; ++ i )  for ( int j = 1; j <= m; ++ j ) {
		coe = rint (); all += coe;
		link ( ++ idx, supT, coe );
		link ( trans ( i, j ), idx, INF );
		link ( trans ( i + 1, j ), idx, INF );
	}
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j < m; ++ j ) {
		coe = rint (); all += coe;
		link ( supS, ++ idx, coe );
		link ( idx, trans ( i, j ), INF );
		link ( idx, trans ( i, j + 1 ), INF );
	}
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j < m; ++ j ) {
		int coe = rint (); all += coe;
		link ( ++ idx, supT, coe );
		link ( trans ( i, j ), idx, INF );
		link ( trans ( i, j + 1 ), idx, INF );
	}
	printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ BZOJ3275 Number - AC

(s,i,a_{i}),(i,t,a_{i})

开始讨论

$c$ 偶数
- $a,b$ 同偶

显然不满足 $\gcd(a,b)=1$ 。

- $a,b$ 同奇

\text{let }a=n^{2}+1,b=m^{2}+1 \\ \begin{aligned} a^{2}+b^{2} &=n^{4}+2n^{2}+m^{4}+2m^{2}+2 \\ &=2(n^{2}+m^{2}+1)+n^{4}+m^{4} \end{aligned}

也不满足 $\gcd(a,b)=1$ 。

好，于是 $c$ 只能为奇数， $a,b$ 必须异奇偶性。

连边显然。

#include <cmath>
#include <cstdio>

using i64 = long long;

const i64 INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct Edge { int to, nxt; i64 cst; } graph[MAXM * 2];

int n, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], tot;

void link ( const int u, const int v, const i64 w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

i64 cud ( const i64 x ) { return x * x; }
bool amaiga ( const i64 a, const i64 b ) { i64 r = sqrt ( cud ( a ) + cud ( b ) ); return r * r == ( cud ( a ) + cud ( b ) ); }
int calcGCD ( const i64 a, const i64 b ) { return ! b ? a : calcGCD ( b, a % b ); }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= tot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to; i64 w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const i64 flow ) {
	if ( u == aim )	return flow;
	i64 used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to; i64 w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			i64 ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

i64 calcMXflow ( const int supS, const int supT ) {
	i64 res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= tot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}

int main () {
	n = rint (); tot = n; static int a[MAXN]; i64 all = 0;
	const int supS = ++ tot, supT = ++ tot;
	for ( int i = 1; i <= n; ++ i )	a[i] = rint ();
	for ( int i = 1; i <= n; ++ i ) {
		all += a[i];
		if ( a[i] & 1 ) {
			link ( supS, i, a[i] );
			for ( int j = 1; j <= n; ++ j ) {
				if ( amaiga ( a[i], a[j] ) && ( ( a[j] & 1 ) ^ 1 ) && calcGCD ( a[i], a[j] ) == 1 )	link ( i, j, INF );
			}
		}
		else	link ( i, supT, a[i] );
	}
	printf ( "%lld\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ BZOJ3774 最优选择 - AC

fuck。

#include <cstdio>

const int INF = 1e9;
const int MAXN = 1e3 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }
template<typename _T> void swapp ( _T& x, _T& y ) { const _T t = x; x = y; y = t; }

struct Edge { int to, nxt, cst; } graph[MAXM * 2];

int n, m, head[MAXM], ecnt = 1, lav[MAXM], q[MAXM], cur[MAXM], tot;

void link ( const int u, const int v, const int w ) {
	graph[++ ecnt] = { v, head[u], w }, head[u] = ecnt;
	graph[++ ecnt] = { u, head[v], 0 }, head[v] = ecnt;
}

int inside ( const int x, const int y ) { return x >= 1 && x <= n && y >= 1 && y <= m; }
int trans ( const int x, const int y ) { return ( x - 1 ) * m + y; }

bool bfs ( const int supS, const int supT ) {
	int h = 1, t = 0;
	for ( int i = 1; i <= tot; ++ i )	lav[i] = 0;
	lav[q[++ t] = supS] = 1;
	while ( h <= t ) {
		int u = q[h ++];
		for ( int i = head[u]; i; i = graph[i].nxt ) {
			int v = graph[i].to, w = graph[i].cst;
			if ( w && ! lav[v] )	lav[q[++ t] = v] = lav[u] + 1;
		}
	}
	return lav[supT];
}

int dfs ( const int u, const int aim, const int flow ) {
	if ( u == aim )	return flow;
	int used = 0;
	for ( int& i = cur[u]; i; i = graph[i].nxt ) {
		int v = graph[i].to, w = graph[i].cst;
		if ( w && lav[v] == lav[u] + 1 ) {
			int ret = dfs ( v, aim, MIN ( flow - used, w ) );
			graph[i].cst -= ret, graph[i ^ 1].cst += ret, used += ret;
			if ( flow == used )	break;
		}
	}
	if ( ! used )	lav[u] = 0;
	return used;
}

int calcMXflow ( const int supS, const int supT ) {
	int res = 0;
	while ( bfs ( supS, supT ) ) {
		for ( int i = 1; i <= tot; ++ i )	cur[i] = head[i];
		res += dfs ( supS, supT, INF );
	}
	return res;
}


int main () {
	n = rint (), m = rint (); tot = ( n * m ) << 1;
	const int supS = ++ tot, supT = ++ tot; int all = 0;
	static int coeA[MAXN][MAXN], coeB[MAXN][MAXN];
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j )	coeA[i][j] = rint ();
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j )	coeB[i][j] = rint ();
	for ( int i = 1; i <= n; ++ i ) for ( int j = 1; j <= m; ++ j ) {
		all += ( coeB[i][j] << 1 );
		int nod = trans ( i, j ) + n * m;
		if ( ( i + j ) & 1 ) {
			link ( nod, supT, coeB[i][j] ), swapp ( coeA[i][j], coeB[i][j] );
			link ( trans ( i, j ), nod, INF );
			if ( inside ( i + 1, j ) )	link ( trans ( i + 1, j ), nod, INF );
			if ( inside ( i, j + 1 ) )	link ( trans ( i, j + 1 ), nod, INF );
			if ( inside ( i - 1, j ) )	link ( trans ( i - 1, j ), nod, INF );
			if ( inside ( i, j - 1 ) )	link ( trans ( i, j - 1 ), nod, INF );
		}
		else {
			link ( supS, nod, coeB[i][j] ), link ( nod, trans ( i, j ), INF );
			if ( inside ( i + 1, j ) )	link ( nod, trans ( i + 1, j ), INF );
			if ( inside ( i, j + 1 ) )	link ( nod, trans ( i, j + 1 ), INF );
			if ( inside ( i - 1, j ) )	link ( nod, trans ( i - 1, j ), INF );
			if ( inside ( i, j - 1 ) )	link ( nod, trans ( i, j - 1 ), INF );
		}
		link ( supS, trans ( i, j ), coeA[i][j] ), link ( trans ( i, j ), supT, coeB[i][j] );
	}
	printf ( "%d\n", all - calcMXflow ( supS, supT ) );
	return 0;
}

∆ CF24D Broken robot - AC

∆ P3211 [HNOI2011]XOR和路径 - AC

∆ NOIP2020 A 排水系统 - AC

∆ NOIP2020 B 字符串匹配 - AC

∆ NOIP2020 C 移球游戏 - AC

∆ HDU6333 Harvest of Apples - AC

∆ UVA10892 LCM Cardinality - AC

∆ LC874 模拟行走机器人 - AC (LeetCode)

∆ LOC3551 教主的魔法 - AC

∆ LOC20004 抄作业 - AC

∆ LOC3563 最大流 - AC

∆ USACO93 Drainage Ditches - AC

∆ LOC5744 The Perfect Stall - AC

∆ LOC8643 奶牛食品 - AC

∆ LOC4051 SDOI2015 星际战争 - AC

∆ LOC5123 网络流 24 题 圆桌聚餐 - AC

∆ LOC5123 网络流 24 题 圆桌聚餐 - AC

∆ P4539 [SCOI2006] zh_tree - AC

∆ P3736 [HAOI2016]字符合并 - AC

∆ AT2433 ケーキの切り分け２ (Cake 2) via JOI2015 Final T2 - IP

∆ CF1296C Yet Another Walking Robot - AC

∆ P4689 Ynoi2016 这是我自己的发明 - AC

∆ P6701 [POI1997] Genotype - AC

∆ P4194 矩阵 - AC

∆ P4843 清理雪道 - AC

∆ POJ3204 伊基的故事 I - 道路重建 - AC

∆ LOC26288 多源汇最大流 - AC

∆ LOC26287 有源汇有上下界最小流 - AC

∆ LOC9371 网络流 24 题 最小路径覆盖问题 - AC

∆ LOC26280 无源汇上下界可行流 - AC

∆ LOC3097 网络流 24 题 最长递增子序列 - AC

∆ HDU4940 无源汇上下界可行流 / Destroy Transportation system - AC

∆ LOC8381 网络流 24题 飞行员配对方案问题 - AC

∆ ZOJ2314 / SGU194 无源汇上下界可行流 Reactor Cooling - AC

∆ LOC26241 开灯问题 - AC

∆ LOC11144 完美数 - AC

∆ LOC11145 诗意狗 - AC

∆ LOC11146 山海 - AC

∆ LOJ6197 法克 - AC

∆ ZOJ2676 网络战争 - AC

∆ LOC5125 网络流 24 题 方格取数 - AC

∆ LOC5151 百步穿杨 - AC

∆ P4174 [NOI2006]最大获利 - AC

∆ LOC3094 网络流 24 题 太空飞行计划问题

∆ UVA1389 Hard Life - AC

∆ P3749 [六省联考2017]寿司餐厅 - AC

∆ P4177 [CEOI2008]order - AC

∆ P3702 [SDOI2017]序列计数 - AC

∆ P2598 [ZJOI2009]狼和羊的故事 - AC

∆ P1935 [国家集训队]圈地计划 - AC

∆ P4313 文理分科 - AC

∆ P1361 小M的作物 - AC

∆ P4210 土地划分 - AC

∆ P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查 - AC

∆ P1646 [国家集训队]happiness - AC

∆ BZOJ3275 Number - AC

∆ BZOJ3774 最优选择 - AC

∆ LOC5123 网络流 24 题圆桌聚餐 - AC

∆ LOC5123 网络流 24 题圆桌聚餐 - AC

∆ LOC9371 网络流 24 题最小路径覆盖问题 - AC

∆ LOC3097 网络流 24 题最长递增子序列 - AC

∆ LOC8381 网络流 24题飞行员配对方案问题 - AC

∆ LOC5125 网络流 24 题方格取数 - AC

∆ LOC3094 网络流 24 题太空飞行计划问题