~~这不是前几天那个妹子吗~~
by EаrringYYR @ 2019-07-16 14:57:49
[传送门](https://www.luogu.org/discuss/show/123539)
by EаrringYYR @ 2019-07-16 14:59:02
姐，我们装汉子装不像的qwq
by gigo_64 @ 2019-07-16 15:00:32
哪题啊
by wxwoo @ 2019-07-16 15:00:46
@[wxwoo](/space/show?uid=116659) 2756
by EаrringYYR @ 2019-07-16 15:01:21
当我没说
by wxwoo @ 2019-07-16 15:01:59
bfs2里加一个vis数组判定是否用过即可
by EаrringYYR @ 2019-07-16 15:09:59
~~~
#include<bits/stdc++.h>
using namespace std;
const int Max=50010;
int edge[Max];
int to[Max];
int first[Max];
int nxt[Max];
int cnt[Max];
int dep[Max];
int n,m,S,T;
int tmp=1,mf,Count;
int wrong[Max];
int vis[Max];
bool check(int x){
return x!=S&&x!=T;
}
void Add(int u,int v,int f){
nxt[++tmp]=first[u];
first[u]=tmp;
to[tmp]=v;
edge[tmp]=f;
nxt[++tmp]=first[v];
first[v]=tmp;
to[tmp]=u;
edge[tmp]=0;
}
void BFS(int now){
memset(dep,0xff,sizeof(dep));
dep[now]=0;
cnt[0]=1;
queue<int> q;
q.push(now);
while(!q.empty())
{
int p=q.front();
q.pop();
for(int i=first[p];i;i=nxt[i]){
if(dep[to[i]]==-1){
++cnt[dep[p] = dep[to[i]]+1];
q.push(to[i]);
}
}
}
}
int DFS(int now,int f){
if(now == T)
{
mf+=f;
return f;
}
int tot=0;
for(int i=first[now];i;i=nxt[i])
{
if(edge[i] && dep[to[i]] == dep[now] -1){
int total=DFS(to[i],min(edge[i],f-tot));
if(total){
edge[i]-=total;
edge[i^1]+=total;
tot+=total;
}
if(tot==f) return tot;
}
}
if(!--cnt[dep[now]])
dep[S]=m+1;
++cnt[++dep[now]];
return tot;
}
void BFS2(int now)
{
queue<int> q;
q.push(now);
wrong[now]=1; vis[now]=1;
while(!q.empty()){
int p=q.front(); q.pop();
for(int i=first[p];i;i=nxt[i])
{
q.push(to[i]);
if(!edge[i]&&!wrong[to[i]]){
if(!check(to[i])||!check(p)) continue;
if(vis[p]||vis[to[i]]) continue;
cout<<p<<' '<<to[i]<<endl;
if(++Count==mf) return;
wrong[i]++;
vis[p]++; vis[to[i]]++;
}
}
}
}
int main()
{
cin>>n>>m;
int st=0,ed=0;
while(cin>>st>>ed)
{
if(st==-1&&ed==-1) break;
Add(st,ed,1);
}
S=0; T=m+1;
for(int i=1;i<=n;i++)
Add(S,i,1);
for(int i=n+1;i<=m;i++)
Add(i,T,1);
BFS(T);
while(dep[S]<m)
DFS(S,0x3FFFFFFF);
if(mf==0) cout<<"No Solution!";
else cout<<mf<<endl;
BFS2(S);
return 0;
}
~~~
现在加了点判
然而死循环MLE
by VeritasatireV @ 2019-07-16 15:12:46
## 试试这个
```
void bfs2(){
queue<int> q;
q.push(s);
vis[s]=true;
while(!q.empty()){
int u=q.front();
q.pop();
for(int e=first[u];e;e=nxt[e]){
q.push(to[e]);
if(w[e]==0&&!vis[to[e]]){
vis[to[e]]=true;
if(u==0||to[e]==0) continue;
if(u==n+1||to[e]==n+1) continue;
cout<<u<<" "<<to[e]<<endl;
ind++;
if(ind==mf) return ;
}
}
}
}
```
by EаrringYYR @ 2019-07-16 15:18:38
A掉了（原因是魔改炸了qwq）
by VeritasatireV @ 2019-07-16 15:40:28