A
题目描述
给定 \(n\) 个数 \(a_i\)，其中 \(k\) 个 \(a_i\) 是奇数，再给定一个 \(n\times n\) 的矩阵 \(\{c_{i,j}\}\)，都保证是非负整数，你可以做下列操作任意次：
- \(a_i\) 减 \(1\)，\(a_j\) 减 \(1\)，花费 \(c_{i,j}\) 的代价，\(i=j\) 是被允许的。
问把所有 \(a_i\) 都变成 \(0\) 的最小花费什么，无解输出 \(-1\)
\(1\leq n\leq 50,k\leq8,c_{i,j}\leq10^5,a_i\leq 100\)
解法
一般图最大匹配是不在我能力范围内的，但是鉴于本题还是匹配问题，我们尽量把问题化归到二分图上去，并且我们合理揣测出题人的意图，把奇数点作为关键点。
首先考虑没有奇数点的情况，如果 \((i,j)\) 之间操作了一次就把他们之间连一条无向边，最后得到一个可能有重边和自环的图，并且满足每个点的度数都是偶数。那么这个图是个欧拉图，也就是我们能找到一种边定向方案，使得所有点的入度等于出度。那么可以得到关键结论：存在最优方案，使得对应的图可以找到一种边定向方案使得所有点入度等于出度。
那么我们拆点，把点 \(i\) 拆成左部点和右部点，分别代表了一个点的入度和出度。那么两部之间可以直接连费用为 \(c_{i,j}\) 的完全二分图，源点向 \(x_{in}\) 连容量 \(\frac{a_i}{2}\) 的边，\(x_{out}\) 向汇点连容量为 \(\frac{a_i}{2}\) 的边，对这个图跑费用流即可。
那么如果有奇数点怎么办？如果我们在图上通过加边的方式把奇数点补成偶数点，那么可以类似地得到结论：存在最优方案，奇数点的入度和出度相差 \(1\)
因为奇数点的数量很少，所以我们花 \(O(2^k)\) 来枚举奇数点的度数，然后跑费用流即可。
总结
二元操作可以通过建边转化到图上去思考。
往已知的问题上化归，这时一定要坚信题目具有某种特殊性。
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int M = 105;
const int inf = 0x3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,ans,a[M],b[M],c[M][M],p[M];
int S,T,tot,f[M],dis[M],pre[M],lst[M],flow[M];
struct edge{int v,f,c,next;}e[M*M];
void add(int u,int v,int F,int c)
{
e[++tot]=edge{v,F,c,f[u]},f[u]=tot;
e[++tot]=edge{u,0,-c,f[v]},f[v]=tot;
}
int bfs()
{
queue<int> q;
for(int i=0;i<=T;i++) dis[i]=inf,flow[i]=0;
q.push(S);dis[S]=0;flow[S]=inf;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v,c=e[i].c;
if(e[i].f>0 && dis[v]>dis[u]+c)
{
dis[v]=dis[u]+c;
pre[v]=u;lst[v]=i;
flow[v]=min(flow[u],e[i].f);
q.push(v);
}
}
}
return flow[T]>0;
}
int work()
{
int res=0;
tot=1;S=0;T=2*n+1;
for(int i=0;i<=T;i++) f[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
add(i,j+n,inf,c[i][j]);
for(int i=1;i<=n;i++)
{
add(S,i,(a[i]+b[i])/2,0);
add(i+n,T,(a[i]-b[i])/2,0);
}
while(bfs())
{
res+=flow[T]*dis[T];int u=T;
while(u)
{
e[lst[u]].f-=flow[T];
e[lst[u]^1].f+=flow[T];
u=pre[u];
}
}
return res;
}
signed main()
{
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
n=read();ans=1e9;
for(int i=1;i<=n;i++)
{
a[i]=read();
if(a[i]%2) p[m++]=i;
}
if(m%2) {puts("-1");return 0;}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c[i][j]=read();
for(int i=0;i<(1<<m);i++)
{
int cnt=0;
for(int j=0;j<m;j++)
{
if(i>>j&1) b[p[j]]=1;
else b[p[j]]=-1,cnt++;
}
if(cnt!=m/2) continue;
ans=min(ans,work());
}
printf("%d\n",ans);
}