神奇RE???
查看原帖
神奇RE???
678625
shicj楼主2024/8/4 11:50

RE #4,WA #6 #10 求调

把 #4.in 输进去,本地正常运行,在线IDE也正常,为啥RE?

My Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
struct edge{
	int v,w,r;
};
vector<edge>G[10001];
bool vis[10001];
int d[10001],p[10001];
bool bfs(){
	memset(d,-1,sizeof(d));
	memset(vis,0,sizeof(vis));
	queue<int>q;
	q.push(s);
	vis[s]=true;
	d[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(auto i:G[u]){
			int v=i.v,w=i.w;
			if(!vis[v]&&w&&d[v]==-1){
				d[v]=d[u]+1;
				vis[v]=true;
				q.push(v);
			}
		}
	}
	if(d[t]==-1)return false;
	else return true;
}
int dfs(int u,int lim){
	if(u==t)return lim;
	for(int i=p[u];i<G[u].size();i++){
		p[u]=i;
		int v=G[u][i].v,w=G[u][i].w,r=G[u][i].r;
		if(d[v]==d[u]+1&&w){
			int tmp=dfs(v,min(lim,w));
			if(tmp){
				G[u][i].w-=tmp;
				G[v][G[u][i].r].w+=tmp;
				return tmp;
			}
			else{
				d[v]=-1;
			}
		}
	}
	return 0;
}
int dinic(){
	int ans=0;
	while(bfs()){
		memset(p,0,sizeof(p));
		while(true){
			int now=dfs(s,0x3f3f3f3f);
			if(now==0)break;
			ans+=now;
		}
	}
	return ans;
}
void add(int u,int v,int w){
//	cout<<"Link "<<u<<"("<<i_pt(u)<<")"<<" to "<<v<<"("<<i_pt(u)<<") ("<<w<<")"<<endl;
//	cout<<u<<" "<<v<<" "<<w<<endl;
	int ru=G[v].size();
	int rv=G[u].size();
	G[u].push_back({v,w,ru});
	G[v].push_back({u,0,rv});
}
int want[10001],ss,k;
bool used[10001][50];
signed main(){
	cin>>k>>m;
	n=m+k+2;
	s=1,t=n;
	//prob 2~m+1
	//type m+2~k+m+1
	for(int i=1;i<=k;i++){
		cin>>want[i];
		ss+=want[i];
		add(m+1+i,t,want[i]);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x;
		add(s,i+1,1);
		for(int j=1;j<=x;j++){
			cin>>y;
			add(i+1,m+1+y,1);
		}
	}
	int ans=dinic();
	if(ans==ss){
		for(int i=1;i<=m;i++){
			for(auto j:G[i+1]){
				if(j.w==0){
					used[i][j.v-m-1]=true;
				}
			}
		}
		for(int i=1;i<=k;i++){
			cout<<i<<":";
			for(int j=1;j<=m;j++){
				if(used[j][i]){
					cout<<" "<<j;
				}
			}
			cout<<endl;
		}
	}
	else{
		cout<<"No Solution!"<<endl;
	}
	return 0;
}
2024/8/4 11:50
加载中...