8 9 W A(网络流求助)
查看原帖
8 9 W A(网络流求助)
214728
剑雪清寒楼主2022/9/17 15:32

rt,89pts,实在找不出错了,以下代码

#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
inline long long read() {
	long long x;bool f;char ch;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	return f?-x:x;
}
inline void print(long long x,char las) {
	if(!x) {
		putchar(48),putchar(las);
		return ;
	}
	if(x<0) putchar('-'),x=-x;
	int ls[20],k=0;
	while(x) ls[++k]=x%10,x/=10;
	while(k) putchar(ls[k--]+48);
	putchar(las);
	return ;
}
struct edge {
	int to,name;long long lim;
	edge *next;
};
struct graph {
	int rs;edge rd[2000002],*head[3002];
	inline void add(int u,int v,long long lim) {
		rd[rs].to=v;rd[rs].lim=lim;rd[rs].name=rs;rd[rs].next=head[u];head[u]=&rd[rs++];
	}
}g1,g2;
int dist[3002],cnt[3022];
int n=read(),s,t;
inline void st() {
	queue<int>que;que.push(t);
	for(int i=0;i<=n;i++) dist[i]=-1;
	dist[t]=0;
	cnt[0]=1;
	while(!que.empty()) {
		int now=que.front();que.pop();
		for(edge *i=g2.head[now];i;i=i->next) {
			int nex=i->to;
			if(dist[nex]==-1) dist[nex]=dist[now]+1,que.push(nex),cnt[dist[nex]]++;
		}
	}
	return ;
}
long long ans=0;
inline long long ISAP(int x,long long lim) {
	if(x==t) {
		ans-=lim;
		return lim;
	}
	long long used=0;
	for(edge *i=g1.head[x];i;i=i->next) {
		int nex=i->to;
		if(i->lim && dist[x]==dist[nex]+1) {
			long long cost=ISAP(nex,min(i->lim,lim-used));
			if(cost) {
				i->lim-=cost;
				g2.rd[i->name].lim+=cost;
				used+=cost;
				if(used==lim) return used;
			}
		}
	}
	for(edge *i=g2.head[x];i;i=i->next) {
		int nex=i->to;
		if(i->lim && dist[x]==dist[nex]+1) {
			long long cost=ISAP(nex,min(i->lim,lim-used));
			if(cost) {
				i->lim-=cost;
				g1.rd[i->name].lim+=cost;
				used+=cost;
				if(used==lim) return used;
			}
		}
	}
	cnt[dist[x]]--;
	if(!cnt[dist[x]]) dist[s]=n+1;
	dist[x]++;
	cnt[dist[x]]++;
	return used;
}
int main() {
	s=0;t=1;
	for(int i=1;i<=n;i++) {
		int a=read();ans+=a;
		g1.add(s,i+1,a),g2.add(i+1,s,0);
	}
	for(int i=1;i<=n;i++) {
		int a=read();ans+=a;
		g1.add(i+1,t,a),g2.add(t,i+1,0);
	}
	int m=read();
	n+=1;
	for(int i=1;i<=m;i++) {
		int k=read(),c=read();ans+=c;
		g1.add(s,n+1,c),g2.add(n+1,s,0);c=read();
		g1.add(n+2,t,c),g2.add(t,n+2,0);ans+=c;
		while(k--) {
			c=read();
			g1.add(n+1,c+1,inf),g2.add(c+1,n+1,0);
			g2.add(c+1,n+2,inf),g2.add(n+2,c+1,0);
		}
		n+=2;
	}
	st();
	while(dist[s]<n) ISAP(s,inf);
	print(ans,'\n');
	return 0;
}
2022/9/17 15:32
加载中...