mcfx's blog - 图论

mcfx's blog - 图论 2016-12-26T10:48:00+08:00 Typecho /feed/atom/category/gr/ <![CDATA[BZOJ 4398: 福慧双修]]> /archives/158/ 2016-12-26T10:48:00+08:00 2016-12-26T10:48:00+08:00 admin

###Description
菩萨为行，福慧双修，智人得果，不忘其本。
——唐朠立《大慈恩寺三藏法师传》
有才而知进退，福慧双修，这才难得。
——乌雅氏
如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有N块区域，M条小路，两块区域之间可通过小路连接起来。现在甄嬛站在1号区域，而她需要在御花园中绕一绕，且至少经过1个非1号区 域的区域。但是恰好1号区域离碎玉轩最近，因此她最后还是要回到1号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出“-1”。

###Input
第一行仅2个正整数n,m，意义如题。
接下来m行每行4个正整数s,t,v,w，其中s,t为小路所连接的两个区域的编号，v为甄嬛从s到t所需的时间，w为甄嬛从t到s所需的时间。数据保证无重边。

###Output
仅一行，为甄嬛回到1号区域所需的最短时间，若方案不存在，则输出-1

###Sample Input
3 3
1 2 2 3
2 3 1 4
3 1 5 2

###Sample Output
8

###Solution
一条合法路径一定是1->a->...->b->1这样的
考虑a和b一定有至少一个二进制位不同
所以按二进制分组，每次新建一个源点和汇点，分别连向某位为1和0的点，然后跑最短路

###Code
```c++
#include<bits/stdc++.h>

#define mp(a,b) std::make_pair(a,b)

int n,p[40001],dis[40001];
bool vis[40001];
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,
    std::greater<std::pair<int,int> > >q;

struct edge
{
	int to,ne,w;
}e[200001];

inline void add(int i,int a,int b,int w)
{
	e[i].to=b,e[i].ne=p[a],e[i].w=w,p[a]=i;
}

inline void yjq(int andv,int anda,int &ans)
{
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	for(int j=p[1];j;j=e[j].ne)
		if((e[j].to&andv)==anda)
			q.push(mp(dis[e[j].to]=e[j].w,e[j].to));
	while(!q.empty())
	{
		int k=q.top().second;q.pop();
		if(vis[k])continue;
		vis[k]=1;
		for(int j=p[k];j;j=e[j].ne)
			if(e[j].to==1)
			{
				if((k&andv)!=anda&&ans>dis[k]+e[j].w)ans=std::min(ans,dis[k]+e[j].w);
			}
			else if(dis[e[j].to]>dis[k]+e[j].w)
			{
				q.push(mp(dis[e[j].to]=dis[k]+e[j].w,e[j].to));
			}
	}
}

int main()
{
	int m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		add(i*2+1,a,b,c);
		add(i*2+2,b,a,d);
	}
	int ans=0x7fffffff;
	for(int i=1;i<=n;i<<=1)
	{
		yjq(i,i,ans);
		yjq(i,0,ans);
	}
	printf("%d",ans);
}
```

]]> <![CDATA[Codeforces 723E.One-Way Reform]]> /archives/47/ 2016-10-03T22:55:00+08:00 2016-10-03T22:55:00+08:00 admin

###Description
There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.

The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.

有一个无向图，n个点，m条边，无自环，无重边，现在要给每个边定方向，使得入度等于出度的点最多

###Input
The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.

Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland.

The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.

It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.

Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.

###Output
For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.

In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once.

###Example
input
2
5 5
2 1
4 5
2 3
1 3
3 5
7 2
3 7
4 2
output
3
1 3
3 5
5 4
3 2
2 1
3
2 4
3 7

###Solution
将度数为奇的边间连上边，然后每次从任一点出发，走过一条边就定为走的方向，直到回到出发点。当所有边被定向后停止操作
那么对于度数为偶数的边，其入度一定等于出度，输出时去掉新加的边

###Code
```c++
#include<bits/stdc++.h>

struct edge
{
    int to,ne;
    bool v;
}e[50000];

int p[201],em=2,deg[201],n,m;
bool ok[50000];

inline void add(int a,int b,bool v)
{
    e[em].to=b,e[em].v=v,e[em].ne=p[a],p[a]=em++;
}

inline void solve()
{
    scanf("%d%d",&n,&m);
    em=2;
    memset(p,0,n*4+4);
    memset(deg,0,n*4+4);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b,1);
        add(b,a,1);
        deg[a]++;
        deg[b]++;
    }
    int lst=0,ans=n;
    for(int i=1;i<=n;i++)
        if(deg[i]&1)
        {
            if(lst)
                add(i,lst,0),add(lst,i,0),deg[i]++,deg[lst]++;
            else
                lst=i;
            ans--;
        }
    memset(ok,0,em);
    lst=1;
    printf("%d\n",ans);
    while(1)
    {
        while(lst<=n&&!deg[lst])lst++;
        if(lst>n)break;
        int k=lst;
        while(1)
        {
            bool f=1;
            for(int i=p[k];i;i=e[i].ne)
                if(!ok[i])
                {
                    f=0,ok[i]=1,ok[i^1]=1;
                    if(e[i].v)printf("%d %d\n",k,e[i].to);
                    deg[k]--;
                    deg[e[i].to]--;
                    k=e[i].to;
                    break;
                }
            if(f)break;
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
}
```

]]>