自动搬运

查看原文

来自洛谷，原作者为

	Miraik 看啊那只蝴蝶 飞过时间 落在心间

搬运于2025-08-24 22:49:25，当前版本为作者最后更新于2023-08-26 20:30:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为 d2t1 可以说是非常优雅的签到题。但是我签不上，蚌埠住了。

题意就是竞赛图求最大流，但暴力跑肯定不行，于是我们考虑转最小割，研究割出的两个点集的性质。

假设起点所在的点集为 $S$，终点所在的点集为 $T=V-S$，那么这个割的大小即 $f(S,T)=\sum\limits_{u \in S} \sum\limits_{v \in T} e_{u,v}$。

考虑竞赛图的性质，我们发现有 $f(S,T)+f(T,S)=|S| \times |T|$，$f(S,T)-f(T,S)=\sum\limits_{u \in S} out_u - in_u$。二式联立容易求得 $f(S,T)$。那么我们需要在 $|S|$ 相同时最小化 $\sum\limits_{u \in S} out_u - in_u$。那我们排序后贪心地取就好了。时间复杂度 $O(nm)$。

#include<bits/stdc++.h>
using namespace std;
inline void chkmin(int &x,int y){ x=min(x,y); }
int n,m,sz,sum,deg[3005],p[3005],vis[3005]; char s[3005];
bool cmp(int x,int y){ return deg[x]<deg[y]; }
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s+1;
		for(int j=1;j<=n;j++) if(s[j]=='1') deg[i]++,deg[j]--;
	}
	for(int i=1;i<=n;i++) p[i]=i;
	sort(p+1,p+n+1,cmp);
	while(m--){
		int t,k,x; cin>>t>>k;
		for(int i=1;i<=n;i++) vis[i]=0; sz=sum=0;
		while(k--) cin>>x,vis[x]=1,sum+=deg[x],sz++;
		int ans=(sum+sz*(n-sz))/2;
		for(int i=1;i<=n;i++){
			if(vis[p[i]]||p[i]==t) continue;
			vis[p[i]]=1; sum+=deg[p[i]]; sz++;
			chkmin(ans,(sum+sz*(n-sz))/2);
		}
		cout<<ans<<'\n';
	}
	return 0;
}