才学疏浅,请求大佬帮助
  • 板块学术版
  • 楼主dshzsh
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/7/24 08:56
  • 上次更新2023/11/6 22:26:55
查看原帖
才学疏浅,请求大佬帮助
200116
dshzsh楼主2020/7/24 08:56
#include<bits/stdc++.h>
#define maxn 2410
#define maxe 3000010
using namespace std;
const int inf=2e9;
long long pre[maxn],dis[maxn],vis[maxn],head[maxn],tot;
long long m,Flow=0;
struct mb
{
	int n;
	int s,t;
	struct node
	{
		int to,net;
		long long val;
	}e[maxe];
	void init(int _n)
	{
		n=_n;
		Flow=0;
		tot=0;
	}
	void add(int u,int v,long long cap)
	{
		e[++tot].to=v;
		e[tot].val=cap;
		e[tot].net=head[u];
		head[u]=tot;
	} 
	void jb(int u,int v,long long w)//建边!!!!! 
	{
		add(u,v,w);
		add(v,u,0);
	}
	int bfs() 
	{
		for(int i=1;i<=n;i++)
			vis[i]=0;
		queue<int> q;
		q.push(s);
		vis[s]=1;
		dis[s]=inf;
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			for(int i=head[x];i;i=e[i].net)
			{
				if(e[i].val==0) continue;
				int v=e[i].to;
				if(vis[v]==1) continue;
				dis[v]=min(dis[x],e[i].val);
				pre[v]=i;
				q.push(v);
				vis[v]=1;
				if(v==t) return 1;
			}
		}
		return 0;
	}
	void update() 
	{
		int x=t;
		while(x!=s)
		{
			int v=pre[x];
			e[v].val-=dis[t];
			e[v^1].val+=dis[t];
			x=e[v^1].to;
		}
		Flow+=dis[t]; 
	}
	void solve(int a,int b)
	{
		s=a,t=b;
		while(bfs())
		{
			update();
		}
	}
};
mb ww;
int main()
{
	int n;
	scanf("%d%d",&n,&m);
	ww.init(n+m+1);
	int res=0;
	for(int i=1;i<=n;i++)
	{
		int x,t;
		scanf("%d%d",&x,&t);
		ww.jb(0,i,x);
		res+=x;
		for(int j=1;j<=t;j++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			ww.jb(i,n+a,b);
		}
	}
	for(int i=1;i<=m;i++)
	{
		int ff;
		scanf("%d",&ff);
		ww.jb(i+n,m+n+1,ff);
	}
	ww.solve(0,n+m+1);
	printf("%lld",res-Flow);
	return 0;
};

P4177

2020/7/24 08:56
加载中...