P9545 [湖北省选模拟 2023] 环山危路 / road

· · 题解

作为 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;
}