星星灰暗着。

[HAOI2017]新型城市化

posted on 2018-05-11 13:45:02 | under 题解 |

#include<cstdio>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstring>
#define neko 10010
#define meko 150010
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
using namespace std;
int n,m,S,T,inf=1e9;
int t=1;
typedef int arr[neko];
template<typename T>
T chkmax(T a,T b)
{return a>b?a:b;}
template<typename T>
T chkmin(T a,T b)
{return a<b?a:b;}
struct node
{int u,v,cap,next;}e[meko<<2];
namespace Flow
{
{
e[++t].v=y;
e[t].u=x;
e[t].cap=z;
e[++t].v=x;
e[t].u=y;
e[t].cap=0;
}
bool bfs()
{
queue<int>q;q.push(S);
memset(dis,0,sizeof(dis)),dis[S]=1;
int u;
while(!q.empty())
{
u=q.front(),q.pop();
travel(i,u,v)
{
if(!dis[v]&&e[i].cap)
{
dis[v]=dis[u]+1;
if(v==T)return 1;
q.push(v);

}
}
}return 0;
}
int dfs(int u,int flow)
{
if(u==T||(!flow))return flow;
int rescap=0,up;
for(register int &i=cur[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
{
if(dis[v]==dis[u]+1&&(up=dfs(v,chkmin(e[i].cap,flow))))
{
e[i].cap-=up,e[i^1].cap+=up;
rescap+=up;
if(!(flow-=up))break;
}
}return rescap;
}
void dinic()
}
struct notnode
{int u,v,next;}E[meko<<2];
struct AC
{int x,y;}ans[meko<<1];
namespace Tarjan
{
int p=0,cnt=0,x;
stack<int>s;
void dfs(int u)
{
dfn[u]=low[u]=++p;
s.push(u);
travel(i,u,v)
{
if(!e[i].cap)continue;
if(!dfn[v])dfs(v),low[u]=chkmin(low[u],low[v]);
else if(!scc[v])low[u]=chkmin(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++cnt,x=1e9;
while(x!=u)
{
x=s.top(),s.pop();
scc[x]=cnt;
}
}
}
}
namespace Solve
{
int t_2=0,now=0;
template<typename T>
void swap(T &x,T &y)
{T trs=x;x=y,y=trs;}
bool cmp(AC a,AC b)
{if(a.x==b.x)return a.y<b.y;return a.x<b.x;}
{
E[++t_2].u=x;
E[t_2].v=y;
}
void dfs(int u,bool color)
{
col[u]=1<<color;
//printf("%d %d\n",u,color);
}
void bipart()
{
f(i,1,n)if(!col[i])dfs(i,1);
for(register int i=1;i<=t_2;i+=2)
{
if(col[E[i].u]<col[E[i].v])swap(E[i].u,E[i].v);
}
}
void countans()
{
//f(i,2,t)printf("%d %d %d\n",e[i].u,e[i].v,e[i].cap);
int u,v;
for(register int i=3;i<=t;i+=2)
{
if(e[i].cap)
{
u=e[i].u,v=e[i].v;
if(u>v)swap(u,v);
if(v==S||v==T)continue;
if(scc[u]^scc[v])ans[++now]=(AC){u,v};
}
}sort(ans+1,ans+now+1,cmp);
printf("%d\n",now);
f(i,1,now)printf("%d %d\n",ans[i].x,ans[i].y);
}
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
S=n+1,T=n+2;
f(i,1,m)
{
scanf("%d%d",&x,&y);
}