Description：

有 $ 2n $ 个人玩拔河，拔河的绳子由左右两段组成，每段绳子上有 $ n $ 个位置，第 $ i $ 个人可以在左边绳子的 $ l_i $ 位置处，也可以在右边绳子的 $ r_i $ 位置处。每个位置上有且仅有一个人。每个人有一个实力值 $ s_i $ ，问对于每一种合法方案两边实力值和之差的绝对值最小是多少。

$1\le n\le 30000,1\le s_i\le 15$

Solution：

把绳子左段看成左部点，右段看成右部点，那么一个人就是一条带权边，如果这个二分图中有点度数为 $1$ ，那么这个人的位置已经确定，否则如果合法，剩下的一定是一堆偶环，因为图是二分图，总共有 $n$ 个人，所以总共有 $2n$ 个度数，而又没有奇度点，且每个点都有连边，那么一定每个点度数都为 $2$ ，把这些偶环都找出来，并统计奇偶边，统计时可以把从左到右的边设为正，从右到左的边设为负，这样再用总数减两倍就可以得到在左边和右边的价值，这样可以 $DP$ ，枚举加到那边，但是这样很不好做，不妨把所有为正的值加起来，再把左右相减取绝对值，就可以变成选或不选，可以背包，但背包的复杂度是 $n\sum s_i$ 的，因为最多有 $O(n)$ 个物品，但我们如果设 $S$ 表示不同价值的物品数，那么最差情况是任意 $s$ 都不同，此时有 $\frac{S(S+1)}2\le 15\times 30000$ ，那么我们把相同权值的物品合起来暴力做多重背包，复杂度就被优化成了 $O(S\sum s)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 60010

struct edge

{

	int fr,to,nxt,v,id;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int v,int id)

{

	++edgenum;e[edgenum].fr = a;e[edgenum].to = b;e[edgenum].v = v;

	e[edgenum].id = id;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int l[MAXN],r[MAXN],s[MAXN];

int maxsum;

int tot = 0,cnt,edg,sum;

int A[MAXN],B[MAXN],C[MAXN * 15];

bool f[MAXN * 15];

bool vis[MAXN]; 

void dfs(int k,int ine)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].id != ine)

		{

			if(vis[e[i].to] && e[i].id != e[edg].id)

			{

				++cnt;

				edg = i;

			}

			else if(!vis[e[i].to])

			{

				s[e[i].to] = s[k] + e[i].v;

				sum += e[i].v;

				dfs(e[i].to,e[i].id);

			}

		}

	}

	return;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d%d%d",&l[i],&r[i],&s[i]);

		add(l[i],r[i] + n,-s[i],i);

		add(r[i] + n,l[i],s[i],i);

	}

	maxsum = 0;

	int ans = 0,ansb = 0;

	memset(s,0,sizeof(s));

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

	{

		if(vis[i])continue;

		cnt = edg = sum = 0;

		dfs(i,0);

		if(cnt != 1)

		{

			puts("-1");

			return 0;

		}

		++tot;

		A[tot] = sum - 2 * s[e[edg].fr] - e[edg].v;

		B[tot] = sum - 2 * s[e[edg].to] + e[edg].v;

		if(A[tot] > B[tot])swap(A[tot],B[tot]);

		B[tot] -= A[tot];C[B[tot]]++;

		maxsum += B[tot];ansb += A[tot];

	}

	ans = abs(ansb);

	f[0] = true;

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

		if(C[i])

			for(int j = maxsum;j >= 0;--j)

				if(f[j])

					for(int k = 1;k <= C[i] && !f[i * k + j];++k)

						f[i * k + j] = 1; 

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

	{

		if(f[i])ans = min(ans,abs(ansb + i));

	}

	cout << ans << endl;

	return 0;

}