「luogu - P4126」「ahoi 2009」最小割

link。

也许题不错，反正有点降智…

先给结论，在

的流网络中：

• 可行边：在增广完的 induced subgraph 中，不存在 \(u\) 到 \(v\) 的路径；
• 必要边：在增广完的 induced subgraph 中，可以从 \(S\) 到 \(u\) 且可以从 \(v\) 到 \(T\)。

先看可行边。不存在 \((u,v)\) 有两个条件，一个是 \(c_f(u,v)=0\)，另一个是与之并联（特指以 \(u\) 为起点，\(v\) 为终点的）的线路中存在 \(c_f(u',v')=0\)。第一个的理解是，如果它没满流，则与之串联的 arcs 中存在比它的容量更小的边，根据最小割串联割最小的原则成立；第二个就是，如果你不把并联的砍了，你的划分压根不合法，何谈可行与否。

那么关于可行边的判断，把图缩点即可。

再看必要边。这个类比可行边即可，不赘述。

#include
using namespace std;
int n,m,S,T,co[4100],dfsnt,colnt,inst[4100],sta[4100],top,dfn[4100],low[4100],vi[4100],rec[60100];
vector> arc;
template struct network {
	const int n;
	struct edge {
		int to,r; T w;
//		friend bool operator<(const edge& one,const edge& ano) { return one.to> e;
	vector lev,iter;
	network(int n):n(n),e(n+1),lev(n+1),iter(n+1) {}
	void link(const int x,const int y,T w,int ID) {
		assert(1<=x && x<=n && 1<=y && y<=n);
		rec[ID]=int(e[x].size());
		e[x].push_back((edge){y,int(e[y].size())+(x==y),w});
		e[y].push_back((edge){x,int(e[x].size())-1,0});
	}
	bool BFS(const int s,const int t) {
		queue q; lev.assign(n+1,0);
		for(q.push(s),lev[s]=1; q.size(); q.pop()) {
			for(int now=q.front(),i=iter[now]=0,y; i::max(),t);
		return res;
	}
};
template T rd() {
	T x=0; char IO=getchar(); bool f=0;
	while(IO<'0' || IO>'9')	f|=IO=='-',IO=getchar();
	while(IO>='0' && IO<='9')	x=x*10+(IO&15),IO=getchar();
	return f?-x:x;
}
void DFS(const int now,const network& G) {
	dfn[now]=low[now]=++dfsnt;
	inst[sta[++top]=now]=1;
	for(int i=0,y; i& G,const int c) {
	vi[now]=c;
	for(int i=0,y; i G(n);
	for(int i=0,x,y; i::edge){arc[i].second,0,0})->to);
//		if(lower_bound(G.e[arc[i].first].begin(),G.e[arc[i].first].end(),(network::edge){arc[i].second,0,0})->w)	puts("0 0");
//		printf(" (%d %d)[%d %d]\n",arc[i].first,G.e[arc[i].first][rec[i]].to,co[arc[i].first],co[G.e[arc[i].first][rec[i]].to]);
		if(G.e[arc[i].first][rec[i]].w)	puts("0 0");
		else	printf("%d %d\n",co[arc[i].first]!=co[arc[i].second],vi[arc[i].first]==1 && vi[arc[i].second]==2);
	}
	return 0;
}