为啥题解要这么建边?
查看原帖
为啥题解要这么建边?
856309
oiyang楼主2023/7/7 19:06

不是一个虚的源点和一个虚的交点就得了吗?

int id(int p,int x) {
	switch(p) {
		case 1: return x;
		case 2: return n2+x;
		case 3: return n2+n1+x;
		case 4: return n2+n1+n1+x;
	}
}



scanf("%d%d%d",&n1,&n2,&n3);
	for(scanf("%d",&m);m--;) {
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(id(1,v),id(2,u),1);
	}
	for(scanf("%d",&m);m--;) {
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(id(3,u),id(4,v),1);
	}
	for(int i=1;i<=n1;++i) addedge(id(2,i),id(3,i),1);
	int S=0,T=n2+n1+n1+n3+1;
	for(int i=1;i<=n2;++i) addedge(S,id(1,i),1);
	for(int i=1;i<=n3;++i) addedge(id(4,i),T,1);
   

为什么从答案到最后的交汇点不能直接连边而是还要加n2+n1+n1?

2023/7/7 19:06
加载中...