自己造数据跟题解跑了几个小时也没出错
(造的数据太水)
求助
#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;
}```