Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
38081 | LYLAKIOIAKIOI | 【BJ】T2 | C++ | 通过 | 100 | 35 MS | 1892 KB | 4291 | 2025-06-12 18:25:03 |
#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define ll long long using namespace std; const int N=2e4+10; const ll inf=1e18+10; const int SZ=1e5+10; bool Mbg; struct dinic{ int tot=1; int hd[SZ],nxt[SZ],to[SZ],cur[SZ]; ll vl[SZ]; void add(int u,int v,ll w){ ++tot; nxt[tot]=hd[u]; to[tot]=v; vl[tot]=w; hd[u]=tot; }void add_edge(int u,int v,ll w){ add(u,v,w); add(v,u,0); }int S,T,cntv,d[SZ],inf=SZ+10; #define go(u,i) for(int i=cur[u];i!=0;i=nxt[i]) bool bfs(){ for(int i=1;i<=cntv;i++) d[i]=inf; queue<int> q;q.push(S);d[S]=0; while(!q.empty()){ int u=q.front();q.pop(); if(u==T) continue; cur[u]=hd[u]; go(u,i){ int v=to[i]; ll w=vl[i]; if(w==0) continue; if(d[v]==inf){ d[v]=d[u]+1; q.push(v); } } } return (d[T]!=inf); }ll dfs(int u,ll flow){ if(flow<=0) return flow; if(u==T) return flow; ll now=flow; go(u,i){ int v=to[i]; ll w=vl[i]; cur[u]=i; if(w==0) continue; if(d[u]+1!=d[v]) continue; ll nd=dfs(v,min(w,now)); vl[i]-=nd,vl[i^1]+=nd; now-=nd; if(now<=0) return flow; }return flow-now; }ll flow(){ ll res=0; while(bfs()) res+=dfs(S,1e18+10); return res; }ll getcap(int x){ return vl[2*x]; }void init(int a,int b,int c){ cntv=a,S=b,T=c; } }mf; struct edge{ int to,a,b; }; vector<edge> E[N]; vector<int> vec; vector<pii> vec2; bool vis[N]; ll flw[N];int bel[N]; char res[N]; struct dsu{ int fa[N]; int fd(int x){ if(x==fa[x]) return x; return fa[x]=fd(fa[x]); }void mg(int x,int y){ x=fd(x),y=fd(y); if(x==y) return ; fa[x]=y; }void init(int n){ for(int i=1;i<=n;i++) fa[i]=i; } }dsu; int n,m; bool Med; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) bel[i]=i; int tot=n;dsu.init(n); for(int i=1;i<=m;i++){ int o,a,b,c;cin>>o; if(o==1){ cin>>a>>b; int i1=bel[dsu.fd(a)]; int i2=bel[dsu.fd(b)]; ++tot; E[i1].push_back((edge){tot,0,(int)1e9+10}); E[i2].push_back((edge){tot,0,(int)1e9+10}); dsu.mg(a,b); bel[dsu.fd(a)]=tot; }else if(o==2){ cin>>a;vis[a]=1; int i1=bel[dsu.fd(a)]; E[i1].push_back((edge){a,0,1}); }else{ cin>>a>>b>>c; int i1=bel[dsu.fd(a)]; ++tot; E[i1].push_back((edge){tot,b,c}); bel[dsu.fd(a)]=tot; } } for(int i=1;i<=n;i++){ if(!vis[i]){ int x=bel[dsu.fd(i)]; E[x].push_back((edge){i,0,1}); } } mf.init(tot+2,tot+1,tot+2); int S=tot+1,T=tot+2; int idx=0; for(int i=1;i<=tot;i++){ for(auto ed:E[i]){ int to=ed.to; int cap=ed.b-ed.a; //cout<<i<<' '<<to<<' '<<cap<<endl; idx++;mf.add_edge(i,to,cap); if(to<=n) vec2.push_back(mk(to,idx)); flw[i]-=ed.a;flw[to]+=ed.a; } }for(int i=1;i<=tot;i++){ if(flw[i]>0){ idx++;vec.push_back(idx); mf.add_edge(S,i,flw[i]); }if(flw[i]<0){ idx++; mf.add_edge(i,T,-flw[i]); } }mf.flow(); bool flg=1; for(auto ed:vec){ if(mf.getcap(ed)!=0) flg=0; }if(!flg){ cout<<"NO"<<endl; }else{ for(auto ed:vec2){ if(mf.getcap(ed.se)!=0){ res[ed.fi]='B'; }else{ res[ed.fi]='R'; } }cout<<"YES"<<endl; for(int i=1;i<=n;i++) cout<<res[i]; } //cerr<<(&Mbg-&Med)/1024.0/1024.0<<endl;//memory return 0; }