题意
给定 \(n\) 个点 \(m\) 条边的无向图,边有边权 \(l\)。
需要将点划分成 \(A,B,C\) 三个集合。
\(A\) 或 \(B\) 内部的边有 \(2l\) 的贡献,\(AC\) 或 \(BC\) 之间的边有 \(l\) 的贡献。
集合 \(A\) 必须包含点 \(a\),集合 \(B\) 必须包含点 \(b\),求最小贡献及其方案。
\(2\le n\le1000,0\le m\le2000\)
题解
这些限制看起来就比较最小割。
观察贡献有 \(2l\),那么一个点是得拆成两个的。
比较意识流地建一下图:对于 \(x,y,l\),连 \((x,y+n,l)\) 和 \((x+n,y,l)\) 两条无向边。
建图之后发现一条边两个端点类型对应的贡献是这样的:
\(ST\) | \(TS\) | \(SS\) | \(TT\) | |
---|---|---|---|---|
\(ST\) | \(2\) | \(0\) | \(1\) | \(1\) |
\(TS\) | \(0\) | \(2\) | \(1\) | \(1\) |
\(SS\) | \(1\) | \(1\) | \(0\) | \(2\) |
\(TT\) | \(1\) | \(1\) | \(2\) | \(0\) |
对比一下要求的矩阵:
\(A\) | \(B\) | \(C\) | |
---|---|---|---|
\(A\) | \(2\) | \(0\) | \(1\) |
\(B\) | \(0\) | \(2\) | \(1\) |
\(C\) | \(1\) | \(1\) | \(0\) |
是前面的子矩阵。
需要保证 \(SS\) 和 \(TT\) 之间不会有贡献。其实直接跑最小割是就对的,因为假如某方案这两者之间有边,不如替换成同一种类型(显然是能够替换的)。
官方题解还有一种理解方式:\(\operatorname{cut}(x\cup y)+\operatorname{cut}(x\cap y)\le \operatorname{cut}(x)+\operatorname{cut}(y)\)。
于是 \(A\) 类点对应 \(ST\),\(B\) 类点对应 \(TS\),额外连边 \((s,a,\inf),(s,b+n,\inf),(a+n,t,\inf),(b,t,\inf)\) 即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2005,M=2e4;
const ll inf=1e18;
int n,m,A,B,tot,s,t,op[N],d[N],b[N],v[M];
ll c[M];
vector<int> e[N];
void add(int x,int y,ll w){
v[tot+1]=x;v[tot]=y;c[tot]=w;
e[x].push_back(tot++);e[y].push_back(tot++);
}
bool bfs(){
fill_n(d+1,t,0);fill_n(b+1,t,0);
queue<int> q;
q.push(s);d[s]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int y:e[x]) if(!d[v[y]]&&c[y])
d[v[y]]=d[x]+1,q.push(v[y]);
}
return d[t];
}
ll dfs(int x,ll w){
if(x==t) return w;
ll res=0;
for(int i=b[x];i<e[x].size();i++){
int y=e[x][i];
if(d[v[y]]!=d[x]+1||!c[y]) continue;
b[x]=i;
ll k=dfs(v[y],min(w,c[y]));
c[y]-=k;c[y^1]+=k;
w-=k;res+=k;
if(!w) return res;
}
return res;
}
void getop(int x){
if(op[x]) return;
op[x]=1;
for(int y:e[x]) if(c[y]) getop(v[y]);
}
int main(){
scanf("%d%d%d%d",&n,&m,&A,&B);
t=(s=n*2+1)+1;
add(s,A,inf);add(s,B+n,inf);
add(A+n,t,inf);add(B,t,inf);
for(int x,y,w;m--;)
scanf("%d%d%d",&x,&y,&w),add(x,y+n,w),add(x+n,y,w),add(y+n,x,w),add(y,x+n,w);
ll ans=0;
while(bfs()) ans+=dfs(s,inf);
getop(s);
printf("%lld\n",ans);
for(int i=1;i<=n;i++)
if(op[i]==op[i+n]) putchar('C');
else putchar(op[i]?'A':'B');
return 0;
}
标签:Kingdom,cut,int,题解,ll,Partition,tot,inf
From: https://www.cnblogs.com/shrshrshr/p/17003194.html