Loading... ## QYQ的图 ### 题目描述 给你一个$n$个点，$m$条边的无向图，每个点有一个非负的权值$c_i$，现在你需要选择一些点，使得每一个点如果没有被选择，则与它有边相连的所有点都被选择。 满足上述条件的点集中，所有选择的点的权值和最小是多少？ ### 输入格式 - 第一行包含两个整$n,m$。 - 第二行包含$n$个整数，其中第$i$个整数代表$c_i$。 - 第三行到第$m+2$行，每行包含两个整数$u,v$，代表点$u$和点$v$之间有一条边。 ### 输出格式 - 输出的第一行包含一个整数，代表最小的权值和。 ### 代码 ```cpp #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$取余的值。 ### 代码 ```cpp #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; } ``` <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/490.html">https://www.starroad.top/archives/490.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：October 11th, 2019 at 03:33 pm © 允许规范转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
