什么症状
  • 板块UVA1184 Air Raid
  • 楼主whileAK
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/12 21:50
  • 上次更新2024/9/13 14:55:24
查看原帖
什么症状
817925
whileAK楼主2024/9/12 21:50

刚做完最小路径覆盖的板子,把代码贺过来就WA了,怎么回事呢

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void rd(int &p){
	p=0;char z=getchar();int f(0);
	while(z>'9'||z<'0'){if(z=='-')f^=1;z=getchar();}
	while(z<='9'&&z>='0')p=(p<<1)+(p<<3)+z-'0',z=getchar();
	if(f)p=-p;
}
void rdl(ll &p){
	p=0;char z=getchar();int f(0);
	while(z>'9'||z<'0'){if(z=='-')f^=1;z=getchar();}
	while(z<='9'&&z>='0')p=(p<<1)+(p<<3)+z-'0',z=getchar();
	if(f)p=-p;
}
const int N=102050;
int n,m,e[N],v[N],nxt[N],hd[N],ct(1);
void link(int x,int y,int z){
	e[++ct]=z;v[ct]=y;nxt[ct]=hd[x];hd[x]=ct;
}
int t,d[N],now[N];
queue<int>q;
bool bfs(){
	memset(d,0,sizeof(d));
	while(q.size())q.pop();
	q.push(0);d[0]=1;int u;
	while(q.size()){
		u=q.front();q.pop();now[u]=hd[u];
		for(int i(hd[u]);i;i=nxt[i]){
			if(e[i]&&!d[v[i]]){
				d[v[i]]=d[u]+1;
				if(v[i]==2*n+1)return true;
				q.push(v[i]);
			}
		}
	}return false;
}
int dinic(int p,int flow){
	if(p==2*n+1)return flow;
	int rest(flow);
	for(int i(now[p]),k;i&&rest;i=nxt[i]){
		now[p]=i;
		if(e[i]&&d[v[i]]==d[p]+1){
			k=dinic(v[i],min(rest,e[i]));
			if(!k)d[v[i]]=0;
			rest-=k;
			e[i]-=k;e[i^1]+=k;
		}
	}return flow-rest;
}
int main(){
	rd(t);
	while(t--){
		ct=1;
		memset(hd,0,sizeof(hd));
		memset(v,0,sizeof(v));
		memset(nxt,0,sizeof(nxt));
		memset(e,0,sizeof(e));
		rd(n);rd(m);
		for(int i(1),x,y;i<=m;++i){
			rd(x);rd(y);
			link(x,y+n,1);link(y+n,x,0);
		}
		for(int i(1);i<=n;++i){
			link(0,i,1);link(i,0,0);
			link(i+n,2*n+1,1);link(2*n+1,i+n,0);
		}int mx(0),x;
		while(bfs())while(x=dinic(0,1e9))mx+=x;
		printf("%d\n",n-mx);
	}
    return 0;
}
2024/9/12 21:50
加载中...