【带花树专题】

PS:...我还是不懂什么是带花树,就只能套套模板了。

下面是几个带花树的题...目前只能找到这点。

Ural-1099 Work scheduling 难度:*

http://acm.timus.ru/problem.aspx?space=1&num=1099

大意:有N个士兵,每个士兵可以另一个士兵巡逻,给出M组士兵愿意在一起巡逻,求出最大的士兵配置方案。

 

分析:直接求最大匹配就好了,然后输出所有的组合

 

ZJU 3316 Game 难度:**

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3316

大意:有N个棋子在棋盘上,2个人轮流拿走一个棋子,第一步可以拿任意一个,而之后每一步必须拿上一步拿走的棋子曼哈顿长度L以内的棋子,问,后手是否能赢

 

分析:把每一个棋子与周围距离为L的棋子都连上边后,形成一些联通块。易知,一轮游戏只能在某一个联通块里开始直到结束。那么,如果有一个联通块不是完美匹配,先手就可以走那个没被匹配到的点,后手不论怎么走,都必然走到一个被匹配的点上,先手就可以顺着这个交错路走下去,最后一定是后手没有路可走,因为如果还有路可走,这一条交错路,就是一个增广路,必然有更大的匹配。

总结:判断是否是完美匹配。

 

HDU 3446 daizhenyang's chess 难度:***

http://acm.hdu.edu.cn/showproblem.php?pid=3446

大意:有一个R*C的棋盘,棋盘上有一些格子是幸运的格子,棋盘上只有一个棋子:king。king有一定的走路范围:20个格子如题中图所示。两个人轮流走,每个人可以移动king走到没被走过的幸运的格子上。问,先手是否能赢。

 

分析:这题与上一题某方面是一样的。都是与增广路有关。把所有能连的边先连上,我们先不算king,求一次匹配。然后我们再算上king,求一次匹配。如果第二次匹配的结果比第一次大,说至少明存在一条增广路,且增广路的起点为king所在的点,那么,我们沿着这条路走下去,最后后手必然无路可走。

总结:2次匹配。

 

HDU 3551 hard problem 难度:****

http://acm.hdu.edu.cn/showproblem.php?pid=3551

大意:给出一个无向图,并给出一个子图的每个点的度数,问是否能去掉一些边,得到这个子图。

 

分析:因为我们要求出这样的一个子图,是删去一些边,使其度数减少,所以,我们先把每条边拆成2个点,(u,e)和(e,v),这两个点连一条边,若匹配这条边表示边e(u,v)不被删除,然后我们把每个点拆成deg[i]-D[i]个点(deg[i]为原图度数,D[i]为子图度数),然后对所有该点和他的边(i,e)组成的点连一条边,表示这个点缺少的度数,可以由这儿得到。接着,求匹配,如果是完美匹配,即:每个度数都找到了可以使他减少的边。这个子图可以得到。

 

总结:让每个需要减少的度数匹配到该点所连接的一条边。

 

下面是我自己用的带花树的模板,暂时没有出现问题:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXE 250*250*2
#define MAXN 250
#define SET(a,b) memset(a,b,sizeof(a))
deque<int> Q;
//g[i][j]存放关系图:i,j是否有边,match[i]存放i所匹配的点
bool g[MAXN][MAXN],inque[MAXN],inblossom[MAXN];
int match[MAXN],pre[MAXN],base[MAXN];

//找公共祖先
int findancestor(int u,int v)
{
    bool inpath[MAXN]={false};
    while(1)
    {
        u=base[u];
        inpath[u]=true;
        if(match[u]==-1)break;
        u=pre[match[u]];
    }
    while(1)
    {
        v=base[v];
        if(inpath[v])return v;
        v=pre[match[v]];
    }
}

//压缩花
void reset(int u,int anc)
{
    while(u!=anc)
    {
        int v=match[u];
        inblossom[base[u]]=1;
        inblossom[base[v]]=1;
        v=pre[v];
        if(base[v]!=anc)pre[v]=match[u];
        u=v;
    }
}

void contract(int u,int v,int n)
{
    int anc=findancestor(u,v);
    SET(inblossom,0);
    reset(u,anc);reset(v,anc);
    if(base[u]!=anc)pre[u]=v;
    if(base[v]!=anc)pre[v]=u;
    for(int i=1;i<=n;i++)
        if(inblossom[base[i]])
        {
            base[i]=anc;
            if(!inque[i])
            {
                Q.push_back(i);
                inque[i]=1;
            }
        }
}

bool dfs(int S,int n)
{
    for(int i=0;i<=n;i++)pre[i]=-1,inque[i]=0,base[i]=i;
    Q.clear();Q.push_back(S);inque[S]=1;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop_front();
        for(int v=1;v<=n;v++)
        {
            if(g[u][v]&&base[v]!=base[u]&&match[u]!=v)
            {
                if(v==S||(match[v]!=-1&&pre[match[v]]!=-1))contract(u,v,n);
                else if(pre[v]==-1)
                {
                    pre[v]=u;
                    if(match[v]!=-1)Q.push_back(match[v]),inque[match[v]]=1;
                    else 
                    {
                        u=v;
                        while(u!=-1)
                        {
                            v=pre[u];
                            int w=match[v];
                            match[u]=v;
                            match[v]=u;
                            u=w;
                        }
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int solve(int n)
{
    SET(match,-1);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(match[i]==-1&&dfs(i,n))
            ans++;
    return ans;
}

PKU 3621-Sightseeing Cows [分数规划/spfa]

题目大意:有一个单向图,可以从任意一点出发,回到该点,每条路都会耗费一定的时间ti。每到一个新的点都会得到一定的分数fi。求一条路使得∑fi/∑ti最大。

题目分析:我们设最优解经过的城市为环 n1->n2->...nk->n1,我们可以猜测最优解的路上不会重复经过一个点(除去出发点)。简略证明:

    假设一个非出发点k被重复经过了,那么k点至少连接了两个环。我们设第一个环的解为:x1 = F1/T1 ,第二个环的解为:x2 = F2/T2。总的解为: x3 = (F1+F2-fk)/(T1+T2)<max(x1,x2)。

    那么最优解为 x' = (fn1+fn2+.....fnk)/(e(n1,n2),e(n2,n3)+....e(nk,n1))。 x' = F/T -> T * x' - F = 0。

    为了求解出这个最优值x',我们设函数 g(x)=T*x-F。这是一个单调函数。所以可以用二分求出答案。

/*

简略证明:

我们设T(y),F(y)为函数(当y不同,表示选取不同的环),设x1<x2,y1 为使 g(x1) 取得最小值的解选择,则:

g(x1) = max(T(y) * x1 - F(y))  = T(y1) * x1 - F(y1) < T(y1)*x2 - F(y1) <=max( T(y)*x2 - F(y) ) = g(x2)

*/

当g(x)>0时,x > x'

当g(x)<0时,x < x'

当g(x)=0时,x = x'

我们可以改变所有边权为 : t*x-f,用spfa求解是否存在负环(g(x)<0),存在增大x,否则减小x

我们把所有没松弛过的点,当成源点,spfa一次...但这题似乎直接对1点松弛也过了,是数据问题??

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 1010
#define MAXE 5050
#define inf 1000000000.0
#define SET(a,b) memset(a,b,sizeof(a))
#define EPS 1e-3

int next[MAXE],p[MAXE],st[MAXN],e;
double dis[MAXN],f[MAXN],c[MAXE];
int used[MAXN],cnt[MAXN];

void add(int a,int b,double d)
{
    next[e]=st[a];
    p[e]=b;
    c[e]=d;
    st[a]=e++;
}

bool spfa(double mid,int S,int N)
{
    int i,j,k;
    queue<int> Q;
    for(i=1;i<=N;i++){
        dis[i]=inf;
        used[i]=0;
    }
    dis[S]=0.0;Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        used[u]=0;
        for(int v=st[u];v!=-1;v=next[v])
        {
            double w=c[v]*mid-f[p[v]];
            if(dis[p[v]]-dis[u]-w>-EPS)
            {
                dis[p[v]]=dis[u]+w;
                if(!used[p[v]])
                {
                    used[p[v]]=1;
                    cnt[p[v]]++;
                    if(cnt[p[v]]>N)return true;
                    Q.push(p[v]);
                }
            }
        }
    }
    return false;
}

int main()
{
    SET(st,-1);e=0;
    int N,M;
    scanf("%d%d",&N,&M);
    int i,j,k;
    double l=0,r=0;
    for(i=1;i<=N;i++)
    {
        scanf("%lf",f+i);
        r+=f[i];
    }
    for(i=1;i<=M;i++)
    {
        int x,y;
        double z;
        scanf("%d%d%lf",&x,&y,&z);
        add(x,y,z);
    }
    while(r-l>EPS)
    {
        double mid=(l+r)/2;
        SET(cnt,0);
        bool flag=false;
        for(i=1;i<=N;i++)
            if(!cnt[i])
            {
                flag=spfa(mid,i,N);
                if(flag)break;
            }
        if(flag)l=mid;
        else r=mid;
    }
    printf("%.2f\n",l);
    return 0;
}