1 条题解

  • 0
    @ 2025-5-25 18:01:22
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    #define INF (1<<30)
    #define MAXN 22
    #define MAXM 8888
    
    struct Edge{
    	int v,cap,flow,next;
    }edge[MAXM];
    int vs,vt,NE,NV;
    int head[MAXN];
    
    void addEdge(int u,int v,int cap){
    	edge[NE].v=v; edge[NE].cap=cap; edge[NE].flow=0;
    	edge[NE].next=head[u]; head[u]=NE++;
    	edge[NE].v=u; edge[NE].cap=0; edge[NE].flow=0;
    	edge[NE].next=head[v]; head[v]=NE++;
    }
    
    int level[MAXN];
    int gap[MAXN];
    void bfs(){
    	memset(level,-1,sizeof(level));
    	memset(gap,0,sizeof(gap));
    	level[vt]=0;
    	gap[level[vt]]++;
    	queue<int> que;
    	que.push(vt);
    	while(!que.empty()){
    		int u=que.front(); que.pop();
    		for(int i=head[u]; i!=-1; i=edge[i].next){
    			int v=edge[i].v;
    			if(level[v]!=-1) continue;
    			level[v]=level[u]+1;
    			gap[level[v]]++;
    			que.push(v);
    		}
    	}
    }
    
    int pre[MAXN];
    int cur[MAXN];
    int ISAP(){
    	bfs();
    	memset(pre,-1,sizeof(pre));
    	memcpy(cur,head,sizeof(head));
    	int u=pre[vs]=vs,flow=0,aug=INF;
    	gap[0]=NV;
    	while(level[vs]<NV){
    		bool flag=false;
    		for(int &i=cur[u]; i!=-1; i=edge[i].next){
    			int v=edge[i].v;
    			if(edge[i].cap!=edge[i].flow && level[u]==level[v]+1){
    				flag=true;
    				pre[v]=u;
    				u=v;
    				aug=min(aug,edge[i].cap-edge[i].flow);
    				if(v==vt){
    					flow+=aug;
    					for(u=pre[v]; v!=vs; v=u,u=pre[u]){
    						edge[cur[u]].flow+=aug;
    						edge[cur[u]^1].flow-=aug;
    					}
    					aug=INF;
    				}
    				break;
    			}
    		}
    		if(flag) continue;
    		int minlevel=NV;
    		for(int i=head[u]; i!=-1; i=edge[i].next){
    			int v=edge[i].v;
    			if(edge[i].cap!=edge[i].flow && level[v]<minlevel){
    				minlevel=level[v];
    				cur[u]=i;
    			}
    		}
    		if(--gap[level[u]]==0) break;
    		level[u]=minlevel+1;
    		gap[level[u]]++;
    		u=pre[u];
    	}
    	return flow;
    }
    int main(){
    	int t,n,a,b;
    	char s[11];
    	scanf("%d",&t);
    	while(t--){
    		scanf("%d%d",&n,&vt);
    		vs=n; NV=n+1; NE=0;
    		memset(head,-1,sizeof(head));
    		for(int i=0; i<n; ++i){
    			scanf("%s",s);
    			if(s[0]=='I') addEdge(vs,i,INF);
    			scanf("%d",&a);
    			while(a--){
    				scanf("%d",&b);
    				addEdge(i,b,INF);
    				addEdge(b,i,1);
    			}
    		}
    		int res=ISAP();
    		if(res>10000000) puts("PANIC ROOM BREACH");
    		else printf("%d\n",res);
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    2085
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    2
    已通过
    1
    上传者