求助大佬!!!蒟蒻求助
  • 板块P3410 拍照
  • 楼主Strange_S
  • 当前回复0
  • 已保存回复0
  • 发布时间2019/8/19 09:51
  • 上次更新2025/1/20 20:08:58
查看原帖
求助大佬!!!蒟蒻求助
76751
Strange_S楼主2019/8/19 09:51
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MA 2005
#define inf 1e9
using namespace std;
int n,m,ans=0,sum=0;
int S,T;
int fis[MA],cur[MA],tot=1;
struct edge{
	int nex,go,d;
}a[MA<<1];
int dep[MA];
inline void add(int u,int v,int w){
	a[++tot].nex=fis[u];
	fis[u]=tot;
	a[tot].go=v;
	a[tot].d=w;
	return ;
}
queue<int>q;
inline bool bfs(int s,int t){
	int i;
	
	memset(dep,0x7f,sizeof(dep));
	memcpy(cur,fis,sizeof(fis));
	while(!q.empty()) q.pop();
	dep[s]=0;
	q.push(s);
	while(!q.empty()){
		int now=q.front();q.pop();
		for(int e=fis[now];e;e=a[e].nex){
			int v=a[e].go;
			if(dep[v]>inf&&a[e].d){
				dep[v]=dep[now]+1;
				q.push(v);
			}
		}
	}
	if(dep[t]<inf) return 1;
	return 0;
}
inline int dfs(int now,int t,int lef){
	if(!lef||now==t) return lef;
	int flow=0,f;
	for(int e=cur[now];e;e=a[e].nex){
		int v=a[e].go;
		cur[now]=e;
		if(dep[v]==dep[now]+1&&(f=dfs(v,t,min(lef,a[e].d)))){
			flow+=f;
			lef-=f;
			a[e].d-=f;
			a[e^1].d+=f;
			if(!lef) break;
		}
	}
	return flow;
}
inline void dinic(int s,int t){
	while(bfs(s,t)){
		ans+=dfs(s,t,inf);
	}
	return ;
}
int main(){
	int i;
	int x;
	S=0;
	T=m+n+1;
	scanf("%d %d",&m,&n);
	for(i=1;i<=m;i++){
		scanf("%d",&x);
		sum+=x;
		add(S,i,x);
		add(i,S,0);
		while(1){
			scanf("%d",&x);
			if(x==0) break;
			add(i,m+x,inf);
			add(m+x,i,0);
		}
	}
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		add(m+i,T,x);
		add(T,m+i,0);
	}
	dinic(S,T);
	cout<<endl;
	printf("%d",sum-ans);
	return 0;
}
2019/8/19 09:51
加载中...