hdu7261 信道定向(绝对值等式+欧拉回路+虚点)

题目

n(n<=2e5)个点，m(m<=1e6)条未定向的有向边

需要为有向边定向，定向完毕后，

计第i个点入度为in[i]，出度为out[i]，则第i个点费用为max(in[i],out[i])，

求一种定向方案，使得n个点的最大费用最小，若有多种方案，任意输出一种

t(t<=100)组样例，sumn不超过2e6，summ不超过1e7

思路来源

gzchenben的ppt

题解

把for改成rep宏定义一直tle 调了2h才发现这个问题

首先，max(a,b)=(a+b+abs(a-b))/2

最小化max(in[i],out[i])，由于in[i]+out[i]是固定的，为点i对应的度，

所以，最小化abs(in[i]-out[i])

对每个连通块对应的图单独考虑，

若图有欧拉回路，则in[i]=out[i]，abs(in[i]-out[i])=0

但是不一定有欧拉回路，有可能会有若干个度为奇数的点

由于总的度数为偶数，显然奇数度的点的个数为偶数个

因此，可以新建一个虚点，连接这若干个点，

新图每个点都是偶数，自然有欧拉回路，

求出后，将原来的边定向，忽略新加的边即可

由于对于奇数度的点来说，abs(in[i]-out[i])至少为1，

所以，等于1情况下，原答案最小

代码1

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=2e5+10,M=2e6+4e5+10;
int t,n,m,u,v,cnt,ed,head[M],deg[M];
int to[M],nex[M],ans[M];
inline void add(int u,int v){
    to[++cnt]=v;
    nex[cnt]=head[u];
    head[u]=cnt;
    ans[(cnt+1)>>1]=-1;
}
void dfs(int u){
    for(int i=head[u];i;i=head[u]){
        head[u]=nex[i];
        int id=(i+1)>>1;
        if(~ans[id])continue;
        ans[id]=i&1;
        dfs(to[i]);
    }
}
void sol(){
    scanf("%d%d",&n,&m);cnt=0;
    for(int i=0;i<=n;++i)head[i]=deg[i]=0;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        deg[u]++;deg[v]++;
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;++i){
        if(deg[i]&1)add(0,i),add(i,0);
    }
    for(int i=0;i<=n;++i){
        dfs(i);
    }
    for(int i=1;i<=m;++i)printf("%d",ans[i]);
    puts("");
}
int main(){
    scanf("%d",&t);
    while(t--){
        sol();
    }
    return 0;
}

代码2

另一种写法时，不实际把虚点建出来，从奇数度的点开始搜，

找出一条条欧拉路径，相当于把奇数度的点两两兑掉

最后再把剩余偶数度的点搜一遍

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=2e5+10,M=N*10;
int t,n,m,u,v,cnt,ed,head[N],deg[N];
int to[M],nex[M],ans[M];
void add(int u,int v){
    to[++cnt]=v;
    nex[cnt]=head[u];
    head[u]=cnt;
}
inline void dfs(int u){
    ed=u;
    for(int i=head[u];i;i=nex[i],head[u]=i){
        int id=(i+1)>>1;
        if(ans[id]==-1){
            ans[id]=(i&1);
            dfs(to[i]);
            break;
        }
    }
}
inline void sol(){
    scanf("%d%d",&n,&m);cnt=0;
    for(int i=0;i<=n;++i)head[i]=deg[i]=0;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        ans[i]=-1;
        deg[u]++;deg[v]++;
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;++i){
        if(deg[i]&1){
            dfs(i);
            deg[ed]--;
        }
    }
    for(int i=1;i<=n;++i){
        dfs(i);
    }
    for(int i=1;i<=m;++i)printf("%d",ans[i]);
    puts("");
}
int main(){
    scanf("%d",&t);
    while(t--){
        sol();
    }
    return 0;
}