QYQ的图

题目描述

给你一个$n$个点，$m$条边的无向图，每个点有一个非负的权值$c_i$，现在你需要选择一些点，使得每一个点如果没有被选择，则与它有边相连的所有点都被选择。

满足上述条件的点集中，所有选择的点的权值和最小是多少？

输入格式

• 第一行包含两个整$n,m$。
• 第二行包含$n$个整数，其中第$i$个整数代表$c_i$。
• 第三行到第$m+2$行，每行包含两个整数$u,v$，代表点$u$和点$v$之间有一条边。

输出格式

• 输出的第一行包含一个整数，代表最小的权值和。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, m, c[51], cnt = 1, head[51], ans = 2147483647, f[51];
struct edge {
    int next, to;
} a[1010];
inline int read() {
    int d = 0;
    char ch = getchar();
    while ( ch < '0' || ch > '9' )
        ch = getchar();
    while ( ch >= '0' && ch <= '9' )
        d = ( d << 3 ) + ( d << 1 ) + ch - 48, ch = getchar();
    return d;
}
inline void add( int x, int y ) {
    a[cnt].next = head[x];
    a[cnt].to = y;
    head[x] = cnt++;
}
void dfs( int x, int sum ) {
    if ( sum >= ans )
        return;
    if ( x > n ) {
        ans = min( ans, sum );
        return;
    }
    f[x]++;
    dfs( x + 1, sum + c[x] );
    f[x]--;
    if ( !f[x] ) {
        for ( register int i = head[x]; i; i = a[i].next )
            f[a[i].to]++;
        dfs( x + 1, sum );
        for ( register int i = head[x]; i; i = a[i].next )
            f[a[i].to]--;
    }
}
int main() {
    n = read();
    m = read();
    for ( register int i = 1; i <= n; i++ )
        c[i] = read();
    for ( register int i = 1; i <= m; i++ ) {
        int x, y;
        x = read();
        y = read();
        if ( x == y )
            f[x]++;
        else {
            add( x, y );
            add( y, x );
        }
    }
    dfs( 1, 0 );
    printf( "%d", ans );
    return 0;
}

N染色

题目描述

试求使用$m$种颜色（可以不用完）对一个各边不相等的$n$边形染色，且相邻两边颜色不同的方案数对$10^9+7$取余的值。

代码

#include <cstdio>
#define ll long long
#define mo 1000000007
using namespace std;
ll n, m, r;
ll ksm( ll a, ll b ) {
    for ( r = 1; b; b >>= 1, a = a * a % mo )
        if ( b & 1 )
            r = r * a % mo;
    return r;
}
int main() {
    freopen( "color.in", "r", stdin );
    freopen( "color.out", "w", stdout );
    scanf( "%lld%lld", &n, &m );
    printf( "%lld\n", ( ksm( m - 1, n ) + ( m - 1 ) * ksm( -1, n ) ) % mo );
    return 0;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/490.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。