本地能过但是交上去错了
查看原帖
本地能过但是交上去错了
701254
Mu_leaf楼主2024/4/11 15:47

大佬求调,感觉是输出那错了

#include <bits/stdc++.h>
#define int long long
#define inf 1e18
using namespace std;
namespace IO
{
	char buff[1<<21],*p1=buff,*p2=buff;
	char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
	template<typename T>
	void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
	template<typename T,typename ...Args>
	void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
	char ch[100];
	template<typename T>
	void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
	template<typename T,typename ...Args>
	void write(T x,Args ...args) {write(x);write(args...);}
	void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
	void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
const int N=114514;
struct edge{
	int to,nxt,val;
}e[N];
int cntedge=1,head[N];
inline void add(int u,int v,int w){
	e[++cntedge].val=w;
	e[cntedge].to=v;
	e[cntedge].nxt=head[u];
	head[u]=cntedge;
}
inline void addedge(int u,int v,int w){
	add(u,v,w);
	add(v,u,0);
}
vector<int> V[N];
int m,n,S=0,T=N-114,dep[N],cur[N],pe[N],o,p[N],tot;
int pk[N];
int vis[N];
string s;
inline int get(int i,int k){
	return i+n*k;
}
bool bfs(){
	queue<int> q;
	q.push(S);
	for(int i=0;i<N;i++) cur[i]=head[i];
	memset(dep,-1,sizeof(dep));
	dep[S]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u==T) return 1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].val>0 && dep[v]==-1){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}return 0;
}
int dfs(int u,int flow){
	if(u==T) return flow;
	int out=0;
	for(int i=cur[u];i;i=e[i].nxt){
		int v=e[i].to;
		cur[u]=i;
		if(e[i].val>0 && dep[v]==dep[u]+1){
			if(v<=n && !pk[v]) pk[v]=1,p[++tot]=v;
			int tmp=dfs(v,min(flow,e[i].val));
			e[i].val-=tmp;
			e[i^1].val+=tmp;
			flow-=tmp;out+=tmp;
			if(flow==0) break;
		}
	}return out;
}
signed main(){
	cin >> m >> n;
	int res=0;
	for(int i=1,c;i<=m;i++){
		cin >> c;
		addedge(S,get(i,0),c);
		res+=c;
		getline(cin,s);
		
		int len=s.length(),id=0;
		s=s+' ';
		for(int j=1;j<=len+1;j++){
			if(s[j]==' ') addedge(get(i,0),get(id,1),inf),V[i].push_back(id),id=0;
			else if(s[j]>='0' && s[j]<='9')id=(id<<1)+(id<<3)+s[j]-48;
		}puts("");
	}
	for(int i=1,c;i<=n;i++) cin >> c,addedge(get(i,1),T,c);
	int ans=0;
	while(bfs()) ans+=dfs(S,inf);
	sort(p+1,p+tot+1);
	for(int i=1;i<=tot;i++){
		cout << p[i] << " \n"[i==tot];
		for(auto x:V[p[i]]){
			if(!vis[x]) pe[++o]=x,vis[x]=1;
		}
	}
	sort(pe+1,pe+o+1);
	for(int i=1;i<=o;i++) cout << pe[i] << " \n"[i==o];
	cout << res-ans;
	return 0 ;
}


2024/4/11 15:47
加载中...