善意的投票&小M的作物 題解
善意的投票：
因為只有\(2\)種意願，不妨讓想睡午覺的和源點連邊，讓不想睡午覺的和匯點連邊。對於每一對好朋友，在他們之間連邊。那麼只要源點和匯點還聯通，就存在一對好友是衝突的，我們現在要做的就是刪去最少的邊，使得源點和匯點孤立，問題轉化為最小割，用最大流求解即可。
#include <bits/stdc++.h>
int n,m;
int S,T;
int head[200000],tot=1;
int cur[200000];
int deep[200000];
std::queue<int>q;
struct edge{
int to;
int nxt;
int flow;
}e[200000];
void add(int x,int y,int flow){
e[++tot]={y,head[x],flow};
head[x]=tot;
e[++tot]={x,head[y],0};
head[y]=tot;
}
bool bfs(){
memset(deep,0,sizeof deep);
deep[S]=1;
q.push(S);
while(!q.empty()){
int X=q.front();
q.pop();
for(int i=head[X];i;i=e[i].nxt){
int y=e[i].to;
if(!deep[y]&&e[i].flow){
deep[y]=deep[X]+1;
q.push(y);
}
}
}
return deep[T];
}
int dfs(int x,int flow){
if(x==T||!flow)
return flow;
int Flow=0;
for(int &i=cur[x];i;i=e[i].nxt){
int y=e[i].to;
if(e[i].flow&&deep[y]==deep[x]+1){
if(int w=dfs(y,std::min(flow,e[i].flow))){
e[i].flow-=w;
e[i^1].flow+=w;
Flow+=w;
flow-=w;
if(!flow)
break;
}
}
}
return Flow;
}
void dinic(){
int maxflow=0;
while(bfs()){
memcpy(cur,head,sizeof head);
while(int w=dfs(S,0x3f3f3f3f))
maxflow+=w;
}
printf("%d\n",maxflow);
}
main(){
scanf("%d%d",&n,&m);
S=n+1;T=S+1;
for(int i=1,x;i<=n;++i){
scanf("%d",&x);
if(x)add(i,T,1);
else add(S,i,1);
}
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
add(x,y,1);
add(y,x,1);
}
dinic();
return 0;
}
再考慮小\(M\)的作物，按照之前的做法，對於每種作物，向源點和匯點分別連對應價值流量大小的邊，考慮那些組合收益，假設我們需要獲得那些作物在\(A\)中的收益，那麼當組合中的所有點都和\(B\)斷開後，我們才能保留這條邊，所以我們可以這樣連邊：源點到這個點對應的點\(x\)，流量為組合中的作物都種在\(A\)的價值，這個點向所有組合中的點連邊，邊權都為\(\infty\)。組合中的作物都對這個點對應的點\(x’\)連邊，流量為\(\infty\)，\(x’\)向匯點連邊，流量為組合都種在\(B\)的價值。
問題得解。
#include <bits/stdc++.h>
#define int long long
int n,kind,S=1,T=2;
int ans;
int head[1000001],tot=1;
int cur[1000000];
int deep[5001];
struct edge{
int to,nxt,flow;
}e[4000000];
std::queue<int>q;
void add(int x,int y,int flow){
e[++tot]={y,head[x],flow};
head[x]=tot;
e[++tot]={x,head[y],0};
head[y]=tot;
}
bool bfs(){
while(!q.empty())q.pop();
memset(deep,-1,sizeof deep);
deep[S]=0;
for(int i=0;i<=tot;++i)
cur[i]=head[i];
q.push(S);
while(!q.empty()){
int X=q.front();
q.pop();
for(int i=head[X],y;i;i=e[i].nxt){
y=e[i].to;
if(deep[y]<0&&e[i].flow){
deep[y]=deep[X]+1;
q.push(y);
if(y==T)
return 1;
}
}
}
return 0;
}
int dfs(int x,int flow){
if(x==T||!flow)
return flow;
int Flow=0;
for(int &i=cur[x],y;i;i=e[i].nxt){
y=e[i].to;
if(e[i].flow&&deep[y]==deep[x]+1){
if(int w=dfs(y,std::min(flow,e[i].flow))){
e[i].flow-=w;
e[i^1].flow+=w;
Flow+=w;
flow-=w;
if(!flow)break;
}
}
}
if(!flow)
deep[x]=-1;
return Flow;
}
void dinic(){
while(bfs())
ans-=dfs(S,1e9);
printf("%lld\n",ans);
}
main(){
scanf("%lld",&n);
for(int i=1,x;i<=n;++i){
scanf("%lld",&x);
add(S,i+2,x);
ans+=x;
}
for(int i=1,x;i<=n;++i){
scanf("%lld",&x);
add(i+2,T,x);
ans+=x;
}
scanf("%d",&kind);
for(int i=1,th,valueA,valueB;i<=kind;++i){
scanf("%lld%lld%lld",&th,&valueA,&valueB);
ans+=valueA+valueB;
add(S,n+2+i,valueA);
add(n+2+i+kind,T,valueB);
for(int j=1,x;j<=th;++j){
scanf("%lld",&x);
add(n+2+i,2+x,1e6);
add(2+x,n+2+i+kind,1e6);
}
}
dinic();
return 0;
}
