TLE 求助
查看原帖
TLE 求助
555065
ChrysanthBlossom楼主2024/6/17 15:08

当前弧我加了啊?

常我卡了啊?

怎么还寄?

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define mkp make_pair
using namespace std;
const int maxn=3e6+7;
namespace MaxFlow{
	int cnt=1,head[maxn],to[maxn<<1],nxt[maxn<<1],rl[maxn<<1];
	int st,ed;
	int pnt;
	void init(int n,int s,int e){
		cnt=1;
		pnt=n;
		st=s;
		ed=e;
	}
	void add(int u,int v,int w){
		++cnt;
		to[cnt]=v;rl[cnt]=w;
		nxt[cnt]=head[u];
		head[u]=cnt;
	}
	void add_edge(int u,int v,int w){
		add(u,v,w);
		add(v,u,0);
	}
	ll dis[maxn];
	queue<int>q;
	const ll inf=1e15;
	bool bfs(){
		for(ri i=1;i<=pnt;i++){
			dis[i]=inf;
		}
		dis[st]=0;
		q.push(st);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(ri e=head[u];e;e=nxt[e]){
				int v=to[e],w=rl[e];
				if(dis[u]+1<dis[v]&&w){
					dis[v]=dis[u]+1;
					q.push(v);
				}
			}
		}
		return (dis[ed]!=inf);
	}
	int now[maxn];
	ll dfs(int u,ll s){
		if(u==ed||!s){
			return s;
		}
		ll res=0;
		for(ri e=now[u];e;e=nxt[e]){
			now[u]=e;
			int v=to[e],w=rl[e];
			if(w&&dis[u]+1==dis[v]){
				ll k=dfs(v,min(1ll*w,s));
				s-=k;
				res+=k;
				rl[e]-=k;
				rl[e^1]+=k;
			}
		}
		if(!res)dis[u]=inf;
		return res;
	}
	ll max_flow(){
		ll ans=0;
		while(bfs()){
			for(ri i=1;i<=pnt;i++){
				now[i]=head[i];
			}
			ans+=dfs(st,inf);
		}
		return ans;
	}
}
int n,m;
int val[maxn];
vector<pair<int,int> >ned[maxn];
int cost[maxn];
const int inf=1e9;
namespace IO {
	int len = 0;
	char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
#define gh()                                                            \
	(iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1,stdin),	\
	(iS == iT ? EOF : *iS++) : *iS++)
	inline int read() {
		char ch = gh();
		int x = 0;
		char t = 0;
		while (ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9')
			x = (x << 3) + (x << 1) + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void putc(char ch) {
		out[len++] = ch;
	}
	template <class T> inline void write(T x) {
		if (x < 0)
			putc('-'), x = -x;
		if (x > 9)
			write(x / 10);
		out[len++] = x % 10 + 48;
	}
	template < > inline void write<const char*> (const char* x) {
		int i=0;
		while(x[i]!='\0') out[len++] = x[i++];
	}
	template < > inline void write<char*> (char* x) {
		int i=0;
		while(x[i]!='\0') out[len++] = x[i++];
	}
	template <class T> inline void write(T x,char a){
		write(x);
		out[len++] = a;
	}
	inline void flush() {
		fwrite(out, 1, len, stdout);
		len = 0;
	}
}
using IO::flush;
using IO::putc;
using IO::read;
using IO::write;
signed main(){
	ios::sync_with_stdio(0);
	n=read();m=read();
	for(ri i=1;i<=n;i++){
		val[i]=read();
		int t;t=read();
		while(t--){
			int a,b;
			a=read();b=read();
			ned[i].emplace_back(mkp(a,b));
		}
	}
	for(ri i=1;i<=m;i++)cost[i]=read();
	int pnt=n+m+2,st=n+m+1,ed=n+m+2;
	MaxFlow::init(pnt,st,ed);
	for(ri i=1;i<=m;i++){
		MaxFlow::add_edge(st,i,cost[i]);
	} 
	for(ri i=1;i<=n;i++){
		MaxFlow::add_edge(i+m,ed,val[i]);
		for(auto x:ned[i]){
			MaxFlow::add_edge(x.first,i+m,x.second);
		}
	}
	int ans=0;
	for(ri i=1;i<=n;i++){
		ans+=val[i];
	}
	write(ans-MaxFlow::max_flow());
	flush();
	return 0;
}
2024/6/17 15:08
加载中...