bzoj 2039 & 洛谷 P1791 人员雇佣 —— 二元关系最小割

时间:2022-06-14 16:20:49

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2039

https://www.luogu.org/problemnew/show/P1791

做法就这样:https://www.cnblogs.com/BearChild/p/6426850.html

如果不是先连边再加边权(话说这样很奇怪啊),而是算好边权再连边,再各种等价改一改,就能快2000ms,能在洛谷上A了...

代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
int const xn=,xm=5e6+;
int n,hd[xn],cur[xn],ct=,to[xm],nxt[xm],dis[xn],S,T;
ll c[xm],inf=1e17;
queue<int>q;
ll rd()
{
ll ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
void ade(int x,int y,ll f){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=f;}
void add(int x,int y,ll f){ade(x,y,f); ade(y,x,);}
bool bfs()
{
memset(dis,,sizeof dis);
dis[S]=; q.push(S);
while(q.size())
{
int x=q.front(); q.pop();
for(int i=hd[x],u;i;i=nxt[i])
if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);
}
return dis[T];
}
ll dfs(int x,ll fl)
{
if(x==T)return fl;
ll ret=;
for(int &i=cur[x],u;i;i=nxt[i])
{
if(dis[u=to[i]]!=dis[x]+||!c[i])continue;
ll tmp=dfs(u,min(fl-ret,c[i]));
if(!tmp)dis[u]=;
c[i]-=tmp; c[i^]+=tmp;
ret+=tmp; if(ret==fl)break;
}
return ret;
}
int main()
{
n=rd(); ll x,ans=; S=; T=n+;
for(int i=;i<=n;i++)x=rd(),add(S,i,x);
for(int i=;i<=n;i++)
{
ll sum=;
for(int j=;j<=n;j++)
{
x=rd(); add(i,j,x<<1ll);
sum+=x;
}
add(i,T,sum); ans+=sum;
}
while(bfs())
{
memcpy(cur,hd,sizeof hd);
ans-=dfs(S,inf);
}
printf("%lld\n",ans);
return ;
}