hdu5348（2015多校5）–MZL's endless loop（搜索）
分类：——–求解策略——–搜索
题目链接：点击打开链接
题目大意：给出n个点，m条无向边，现在要求将无向边变为有向边，要保证每个点的出度和入度的差不超过1
直接进行搜索，对每个点进行出度和入度的判断，如果出度大，就先进行反向的搜索(每搜索一条边u,v就认为这是一条v到u的有向边)，反之，进行正向搜索(每搜到一条边u,v认为这是一条u到v的有向边)，一直搜索到找不到边能继续为止。
注意：
1、已经使用过的边为了防止再次被遍历，可以修改head,head[u] = edge[i].next
2、注意自环，因为搜索是判断能不能继续向下搜索时，使用了v的入度和出度比较，那么如果是自环可能会被判断不能被加上。
证明不会有-1的情况，对于一个点v，假设入度比出度多2，那么，第一：就会有一条边搜索到v后找不到后继，导致v的入度比出度多1，第二：又有一条边搜索到v，导致v的入度比出度多2，但是这样的话就会和第一条找不到后继冲突，所以不会出现入度比出度多2的情况，，（其他情况也是类似），所以不会有-1的结果。
#include <cstdio>#include <cstring>#include <queue>#include <set>#include <vector>#include <cmath>#include <map>#include <stack>#include <algorithm>using namespace std ;#pragma comment(linker, "/STACK:102400000,102400000")#define LL __int64#define INF 0x3f3f3f3f#define PI acos(-1.0)const int mod = 1e9+7 ;const double eqs = 1e-9 ;struct node{int u , v , id ;int next ;}edge[700000];int head[100010] , cnt , vis[700000] ;int in[100010] , out[100010] , num[100010] ;int ans[700000] , n ;void add(int u,int v,int id) {edge[cnt].u = u ; edge[cnt].v = v ;edge[cnt].id = id ;edge[cnt].next = head[u] ; head[u] = cnt++ ;}void dfs1(int u) {int i , v ;for(i = head[u] ; i != -1 ; i = edge[i].next ) {if( vis[i] ) {head[u] = edge[i].next ;continue ;}v = edge[i].v ;if( u != v && in[v] > out[v] ) continue ;vis[i] = vis[i^1] = 1 ;if( i%2 ) ans[i/2] = 0 ;else ans[i/2] = 1 ;out[u]++ ;in[v]++ ;head[u] = edge[i].next ;dfs1(v) ;break ;}}void dfs2(int u) {int i , v ;for(i = head[u] ; i != -1 ; i = edge[i].next) {if( vis[i] ) {head[u] = edge[i].next ;continue ;}v = edge[i].v ;if( u != v && out[v] > in[v] ) continue ;vis[i] = vis[i^1] = 1 ;if( i%2 ) ans[i/2] = 1 ;else ans[i/2] = 0 ;out[v]++ ;in[u]++ ;head[u] = edge[i].next ;dfs2(v) ;break ;}}int main() {int t , m ;int i , j , u , v ;scanf("%d", &t) ;while( t– ) {scanf("%d %d", &n, &m) ;cnt = 0 ;for(i = 1 ; i <= n ; i++) {head[i] = -1 ;in[i] = out[i] = num[i] = 0 ;}for(i = 0 ; i <= 2*m ; i++)vis[i] = 0 ;for(i = 0 ; i < m ; i++) {scanf("%d %d", &u, &v) ;add(u,v,i) ;add(v,u,i) ;num[u]++ ;num[v]++ ;}for(i = 1 ; i <= n ; i++) {while( in[i] + out[i] < num[i] ) {if( in[i] >= out[i] )dfs1(i) ;elsedfs2(i) ;}}for(i = 0 ; i < m ; i++) {printf("%d\n", ans[i]) ;}}return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇poj3440–Coin Toss（几何上的概率）下一篇hdu5351（2015多校5）–MZL's Border（打表，，找规律）
顶2踩0
生命有限，努力无限
