Rt,一样的题,CF AC了,UVa WA。
CF的题要加文操,我在UVa上加不加文操都WA,是没有SPJ还是怎样?
CF提交见https://codeforces.com/gym/101308/status
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int u,v;
long long c,w,d;
};
struct LimitMax{
const static int N=100005;
int n,m,s,t;
vector<Edge>E;
vector<int>to[N];
int d[N],C[N];//去掉了当前弧优化 | 又加上了(
bool vis[N];
long long val[N];
void clear(int n){
for(int i=1;i<=n;i++)
to[i].clear();
to[N-1].clear();
to[N-2].clear();
memset(val,0,sizeof(val));
E.clear();
}
void NativeAE(int u,int v,long long w){
E.push_back({u,v,w,0});
E.push_back({v,u,0,0});
m=E.size();
to[u].push_back(m-2);
to[v].push_back(m-1);
}
void AddEdge(int u,int v,long long c,long long d){
n=max(n,max(u,v));
val[u]-=c;
val[v]+=c;
NativeAE(u,v,d-c);
E[m-2].d=c;
}
bool bfs(){
memset(vis,0,sizeof(vis));
queue<int>que;
que.push(s);
d[s]=0;
vis[s]=1;
while(!que.empty()){
int cur=que.front();
que.pop();
for(int i=0;i<to[cur].size();i++){
Edge& x=E[to[cur][i]];
if(!vis[x.v]&&x.c>x.w){
vis[x.v]=1;
d[x.v]=d[cur]+1;
que.push(x.v);
}
}
}
return vis[t];
}
long long dfs(int u,long long v){
if(u==t||v==0)
return v;
long long w=0,f;
for(int i=C[u];i<to[u].size();i++){
C[u]=i;
Edge& e=E[to[u][i]];
if(d[u]+1==d[e.v]&&(f=dfs(e.v,min(v,e.c-e.w)))>0){
e.w+=f;
E[to[u][i]^1].w-=f;
w+=f;
v-=f;
if(v==0)
break;
}
}
return w;
}
long long NativeMF(int s,int t){
this->s=s;
this->t=t;
long long res=0;
while(bfs()){
memset(C,0,sizeof(C));
res+=dfs(s,1e18);
}
return res;
}
long long Maxflow(int s,int t){
long long ans[2]={},sum=0;
for(int i=1;i<=n;i++){
if(val[i]>0){
NativeAE(N-2,i,val[i]);
sum+=val[i];
}
if(val[i]<0)
NativeAE(i,N-1,-val[i]);
}
NativeMF(N-2,N-1);
NativeAE(t,s,1e16);
NativeMF(N-2,N-1);
return E[m-2].w;
}
void print(int p){
if(p==2)
return;
if(p-2>0)
printf("%d ",p-2);
for(int i=0;i<to[p].size();i++){
Edge &e=E[to[p][i]];
if(e.w>0){
e.w--;
print(e.v);
return;
}
}
}
}R;
bool _(int u,int v){
return R.E[u].v<R.E[v].v;
}
int n;
long long ans;
int main(){
scanf("%d",&n);
for(int i=1,u;i<=n;i++){
scanf("%d",&u);
R.AddEdge(1,i+2,0,1e9);
R.AddEdge(i+2,2,0,1e9);
for(int j=1,v;j<=u;j++){
scanf("%d",&v);
R.AddEdge(i+2,v+2,1,1e9);
}
}
for(int i=0;i<R.m;i++)
sort(R.to[i].begin(),R.to[i].end(),_);
printf("%lld\n",ans=R.Maxflow(1,2));
for(int i=0;i<R.m;i++)
R.E[i].w+=R.E[i].d;
while(ans--){
R.print(1);
puts("");
}
}/*
*/