求助,
查看原帖
求助,
122794
tuya_楼主2021/5/16 20:07

自己造数据跟题解跑了几个小时也没出错

(造的数据太水)

求助

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#include <set>
#include <queue>
using namespace std;

const int maxn = 10010;
struct bian{
	int u,v,nex,flow,size;
}e[maxn * 40];
int n,m,fir[maxn],T,S;
vector<int> po[maxn];

int tot = -1;
void add(int a,int b,int w){
	e[++tot].u = a;e[tot].v = b;e[tot].size = 1;
	e[tot].nex = fir[a];fir[a] = tot;
	e[++tot].u = b;e[tot].v = a;e[tot].size = 0;
	e[tot].nex = fir[b];fir[b] = tot;
}

queue<int> q;
int vis[maxn],du[maxn];
vector<int> poi[2];
vector<int> ee[maxn];

void print(int a){
	for(int i = 0;i < poi[a].size(); i++) cout<<poi[a][i]<<" ";
	cout<<endl;
}

void pre(int c,int x){
	vis[x] = c;
	for(int i = 0;i < ee[x].size(); i++){
		vis[ee[x][i]] = (c ^ 1);
	}
}

void init(){
	memset(fir,-1,sizeof fir);
	scanf("%d%d",&n,&m);
	
	for(int i = 1;i <= m; i++){
		int a,b;
		scanf("%d%d",&a,&b);
	//	cout<<a<<" "<<b<<endl;
		ee[a].push_back(b);
		ee[b].push_back(a);
	}
	
	//flood();
	T = 0; S = n + 1;
	
	for(int i = 1;i <= n; i++) if(!vis[i]) pre(2,i);
	
	for(int i = 1;i <= n; i++){
		if(vis[i] == 2){
			add(T,i,1);
			for(int j = 0;j < ee[i].size(); j++){
				add(i,ee[i][j],1);
			}
		}
		else add(i,S,1);
	}
	return ;
}

int cur[maxn];

queue<int> qu;
bool bfs(){
	while(!qu.empty()) qu.pop();
	for(int j = T;j <= S; j++) du[j] = 0;
	du[T] = 1;
	qu.push(T);
	while(!qu.empty()){
		int now = qu.front();
		qu.pop();
		for(int i =fir[now];i != -1;i = e[i].nex){
			if(e[i].flow >= e[i].size) continue;
			int to = e[i].v;
			if(du[to]) continue;
			du[to] = du[now] + 1;
			qu.push(to);
		}
	}
	return du[S] > 0;
}

int dfs(int x,int flo){
	if(x == S || flo == 0) return flo;
	int ans = 0;
	for(;cur[x] != -1;cur[x] = e[cur[x]].nex){
		int to = e[cur[x]].v;
		if(e[cur[x]].flow >= e[cur[x]].size || du[to] != du[x] + 1) continue; 
		
		int son = dfs(to,min(flo,e[cur[x]].size - e[cur[x]].flow));
		
		ans += son;
		flo -= son;
		e[cur[x]].flow += son;
		e[cur[x] ^ 1].flow -= son;
		if(flo == 0) return ans;
		
	}
	return ans;
}

int ans = 0;
void dinic(){
	while(bfs()){
		for(int i = T;i <= S; i++) cur[i] = fir[i];
		ans += dfs(T,maxn * 1000);
	}
//	cout<<ans<<endl;
	return ;
}

int dfn[maxn],low[maxn],tal,co[maxn],color;
bool vv[maxn];
stack<int> s;
void tar(int x){
	//cout<<x<<" "<<endl;
	dfn[x] = low[x] = ++tal;
	s.push(x);
	vv[x] = 1;
	for(int j = fir[x];j != -1;j = e[j].nex){
		if(e[j].flow >= e[j].size) continue;
		int to = e[j].v;
		if(to == T || to == S) continue;
		if(!dfn[to]) {
			//cout<<x<<" "<<to<<endl;
			tar(to);
			low[x] = min(low[x],low[to]);
		}
		else if(vv[to])
		    low[x] = min(low[x],dfn[to]);
	}
    if(dfn[x] == low[x]){
    	int y;
    	color++;
    	do{
    		y = s.top();
    		co[y] = color;
    		vv[y] = 0;
    		s.pop();
		}while(y != x);
	}
	return ;
}

bool evis[maxn * 40];
set<pair<int,int> > an;
int antot;

vector<pair<int,int> > aa;

int main(){
	init();
	
	dinic();
	
	for(int i = 1;i <= n; i++){
		if(!dfn[i]) {
			tar(i);
		}
	}

	for(int i = 1;i <= n; i++){
		if(vis[i] == 2){
			//cout<<"ww"<<i<<endl;
			for(int j = fir[i];j != -1;j = e[j].nex){
				int to = e[j].v;
				
				if(e[j].size - e[j].flow > 0) continue;//cout<<to<<" ";
				if(to == S || to == T) continue;
				if(co[i] != co[to]) aa.push_back(make_pair(min(i,to),max(i,to)));
			}
			//cout<<endl;
		}
	}
	sort(aa.begin(),aa.end());
	printf("%d\n",aa.size());
	for(int i = 0;i < aa.size(); i++){
		printf("%d %d\n",aa[i].first,aa[i].second);
	}
	
	
	return 0;
}```
2021/5/16 20:07
加载中...