集训Day6

今天的图论题略多

但好像都是noip题

bzoj3624

有一个图，边是黑色或者白色，求一个生成树满足恰好有k条白边

贪心

我们把最小生成树上的白边叫做“富家子弟”，把不在树上的叫“贫下中农”

很明显，如果富家子弟超过k个，无解

否则我们先记录富家子弟，然后加入若干贫下中农直至有k条白边

然后加入剩下的黑边让图连通即可

bzoj4596

一个不超过17个点的无重边无自环的图

每个公司可以建一个集合里的边

一共n个点n个公司

求一个生成树满足这n-1个点分别由n-1个公司建成

矩阵树板子题

考虑容斥原理

答案为

[最小生成树的数量]-[一个公司没有建的数量]+[两个公司没有建的数量] ...

二进制枚举一下就可以了，毕竟17

bzoj3007

一个$r \times c$的矩形

从$(1,1)$走一条路径到$(r,c)$

这个矩形里有n个boss，你的路径要满足离boss的最近距离最远

$n \leq 3000$

首先，根据题目描述我们可以二分答案/滑稽

我们二分到一个mid就是以所有boss为圆心，mid为半径画一个圆

用最小割思想建出对偶图（反向对偶¿

原图矩形左下到右上连通等价于对偶图里左下到右上不连通

我们用画出的圆做一下noip2017D2T1的并查集就可以了

（我没见过自己鞭尸自己的

#include <iostream>

#include <cstdio>

#include <cctype>

using namespace std;

const int maxn = ;

const int maxm = ;

int n, m, k, fa[maxn], cnt0, cnt1, num;

bool chs[maxm];

struct edge

{

    int u, v, c;

} e[maxm];

inline int read()

{

    int x=,f=;char ch;

    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-f;

    for(;isdigit(ch);ch=getchar())x=*x+ch-'';

    return x*f;

}

int find(int u)

{

    return fa[u] == u ? u : fa[u] = find(fa[u]);

}

int main()

{

    n = read();

    m = read();

    k = read();

    for (int i = ; i <= n; i++) fa[i] = i;

    for (int i = ; i <= m; i++)

    {

        e[i].u = read();

        e[i].v = read();

        e[i].c = read();

    }

    for (int i = ; i <= m; i++)

    {

        if (e[i].c == )

        {

            int r1 = find(e[i].u);

            int r2 = find(e[i].v);

            if (r1 != r2)

            {

                fa[r1] = r2;

                ++cnt1;

            }

        }

    }

    for (int i = ; i <= m; i++)

    {

        if (e[i].c == )

        {

            int r1 = find(e[i].u);

            int r2 = find(e[i].v);

            if (r1 != r2)

            {

                chs[i] = ;

                fa[r1] = r2;

                ++cnt0;

            }

        }

    }

    if (cnt0 + cnt1 != n -  || cnt0 > k)

    {

        printf("no solution\n");

        return ;

    }

    for (int i = ; i <= n; i++) fa[i] = i;

    cnt0 = cnt1 = ;

    for (int i = ; i <= m; i++)

    {

        if (chs[i])

        {

            int r1 = find(e[i].u);

            int r2 = find(e[i].v);

            if (r1 != r2)

            {

                fa[r1] = r2;

                ++cnt0;

            }

        }

    }

    for (int i = ; i <= m; i++)

    {

        if (e[i].c ==  && cnt0 < k)

        {

            int r1 = find(e[i].u);

            int r2 = find(e[i].v);

            if (r1 != r2)

            {

                chs[i] = ;

                fa[r1] = r2;

                ++cnt0;

            }

        }

    }

    if (cnt0 != k)

    {

        printf("no solution\n");

        return ;

    }

    for (int i = ; i <= m; i++)

    {

        if (e[i].c == )

        {

            int r1 = find(e[i].u);

            int r2 = find(e[i].v);

            if (r1 != r2)

            {

                chs[i] = ;

                fa[r1] = r2;

            }

        }

    }

    for (int i = ; i <= m; i++)

        if (chs[i])

            printf("%d %d %d\n", e[i].u, e[i].v, e[i].c);

    return ;

}

#include<bits/stdc++.h>

#define LL LL

using namespace std;

const int N=,M=;

const int mod=1e9+;

struct node{int x,y;}t[M][N];

LL C[M][M];int m[M];

LL Guass(int n)

{

    LL ans=;

    for(int i=;i<=n;i++)

    {

        for(int j=i+;j<=n;j++)

        {

            LL a=C[i][i],b=C[j][i];

            while(b)

            {

                LL temp=a/b;a%=b;swap(a,b);

                for(int k=i;k<=n;k++) C[i][k]=(C[i][k]-temp*C[j][k]%mod+mod)%mod,swap(C[i][k],C[j][k]);

                ans=-ans;

            }

        }

        if(!C[i][i]) return ;

        ans=ans*C[i][i]%mod;

    }

    ans=(ans%mod+mod)%mod;

    return ans;

}

int main()

{

    int n;scanf("%d",&n);

    for(int i=;i<n;i++)

    {

        scanf("%d",&m[i]);

        for(int j=;j<=m[i];j++) scanf("%d%d",&t[i][j].x,&t[i][j].y);

    }

    LL ans=;

    for(int i=;i<(<<n-);i++)

    {

        memset(C,,sizeof(C));

        int num=;

        for(int j=;j<n;j++)

        {

            if(!(i&(<<j-))) continue;

            num++;

            for(int k=;k<=m[j];k++)

            {

                int a=t[j][k].x,b=t[j][k].y;

                C[a][b]--;C[b][a]--;

                C[a][a]++;C[b][b]++;

            }

        }

        if((n--num)%) ans-=Guass(n-);

        else ans+=Guass(n-);

        ans=(ans%mod+mod)%mod;

    }

    printf("%lld\n",ans);

    return ;

}

#include <bits/stdc++.h>

#define N 3010

using namespace std;

int f[N];

double x[N] , y[N];

int find(int x)

{

    return x == f[x] ? x : f[x] = find(f[x]);

}

void merge(int x , int y)

{

    int tx = find(x) , ty = find(y);

    if(tx != ty) f[tx] = ty;

}

int main()

{

    int n , i , j , cnt = ;

    double a , b , l =  , r , mid;

    scanf("%d%lf%lf" , &n , &a , &b) , r = min(a , b);

    for(i =  ; i <= n ; i ++ ) scanf("%lf%lf" , &x[i] , &y[i]);

    while(cnt -- )

    {

        mid = (l + r) / ;

        for(i =  ; i <= n +  ; i ++ ) f[i] = i;

        for(i =  ; i <= n ; i ++ )

        {

            if(mid >= x[i] -  || mid >= b - y[i]) merge(i , );

            if(mid >= a - x[i] || mid >= y[i] - ) merge(i , n + );

            for(j =  ; j < i ; j ++ )

                if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <=  * mid * mid)

                    merge(i , j);

        }

        if(find() == find(n + )) r = mid;

        else l = mid;

    }

    printf("%.2lf\n" , l);

    return ;

}

巴特西

集训Day6

最新文章

热门文章