BZOJ 2929 网络流

时间:2023-03-09 16:30:55
BZOJ 2929 网络流

题意是啥…….

思路:

不是与1或n连起来的边 边权是1

否则是inf

跑网络流

//By SiriusRen
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=66666,inf=0x3f3f3f3f;
queue<int>q;
int n,num,yy,ans,jy,w[N],v[N],first[N],next[N],tot,vis[N];
void add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}
bool tell(){
memset(vis,-1,sizeof(vis)),vis[1]=0;
queue<int>q;q.push(1);
while(!q.empty()){
int t=q.front();q.pop();
for(int i=first[t];~i;i=next[i])if(w[i]&&!~vis[v[i]])
vis[v[i]]=vis[t]+1,q.push(v[i]);
}return ~vis[n];
}
int zeng(int x,int y){
if(x==n)return y;
int r=0;
for(int i=first[x];~i;i=next[i])if(vis[v[i]]==vis[x]+1&&w[i]){
int t=zeng(v[i],min(y-r,w[i]));
w[i]-=t,w[i^1]+=t,r+=t;
}
if(!r)vis[x]=-1;
return r;
}
int main(){
memset(first,-1,sizeof(first));
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d",&num);
while(num--){
scanf("%d",&yy);
if(yy!=n&&i!=1)add(i,yy,inf),add(yy,i,0);
else add(i,yy,1),add(yy,i,0);
}
}
while(tell())while(jy=zeng(1,inf))ans+=jy;
printf("%d\n",ans);
}