正文

HDU 5348 MZL's endless loop

IP云
IP云V管理员/3 阅读
09/21
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

乱搞题...第一直觉是混合图的欧拉通路，但是感觉并没有多大关系。最终AC的做法是不断的寻找欧拉通路，然后给边标号。所有边访问了一遍，所有点访问了一遍，效率是o(n+m)。不存在-1的情况。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;const int maxn=;
int n,m;
struct Edge
{
int from,to;
int ans;
int flag;
} edge[*maxn+];
vector<int> G[maxn+];
int tot[maxn+];
int Ru[maxn+];
int Ch[maxn+];
int St[maxn+];void dfs(int now,int x)
{
for(int i=St[now]; i<G[now].size(); i++)
{
Edge &e=edge[G[now][i]];
if(!e.flag)//这条边没走过
{
St[now]=i+;
if(x==)
{
if(e.from==now)
{
e.ans=;
e.flag=;
tot[e.from]--;
tot[e.to]--;
Ch[e.from]++;
Ru[e.to]++;
dfs(e.to,x);
return; }
else if(e.to==now)
{
e.ans=;
e.flag=;
tot[e.from]--;
tot[e.to]--;
Ch[e.to]++;
Ru[e.from]++;
dfs(e.from,x);
return;
}
}
else if(x==)
{
if(e.to==now)
{
e.ans=;
e.flag=;
tot[e.from]--;
tot[e.to]--;
Ru[e.to]++;
Ch[e.from]++;
dfs(e.from,x);
return;
}
else if(e.from==now)
{
e.ans=;
e.flag=;
tot[e.from]--;
tot[e.to]--;
Ru[e.from]++;
Ch[e.to]++;
dfs(e.to,x);
return;
}
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
for(int y=; y<=T; y++)
{
scanf("%d%d",&n,&m);
for(int i=; i<=n; i++) G[i].clear();
memset(tot,,sizeof(tot));
memset(Ru,,sizeof(Ru));
memset(Ch,,sizeof(Ch));
memset(St,,sizeof(St));
for(int i=; i<=m; i++)
{
scanf("%d%d",&edge[i].from,&edge[i].to);
if(edge[i].from==edge[i].to)
{
edge[i].ans=;
continue;
}
edge[i].flag=;
G[edge[i].from].push_back(i);
G[edge[i].to].push_back(i);
tot[edge[i].from]++;
tot[edge[i].to]++;
}
for(int i=; i<=n; i++)
{
while(tot[i])
{
if(Ru[i]>=Ch[i]) dfs(i,);
else dfs(i,);
}
}
for(int i=; i<=m; i++)
printf("%d\n",edge[i].ans);
}
return ;
}