2021銀川Problem D. Farm
（注：由于沒有數據，暫不保證正確性）

題意：

有n個點，m個有權邊，有q個限制條件，每個限制條件有兩個選擇：選u個邊，選第v個邊，兩個選擇至少要選一個。
問聯通所有邊的最小花費是多少？
0<=q<=16
1<=n<=1e5
1<=m<=5e5

題解：

不難看出q很小，因此我們可以用二進制的方法直接枚舉直接枚舉每個選擇的情況。比如第i位是0表示第i個選擇選的是邊u，否則選的邊v
這樣復雜度是$O(2^{16}ElogE)$,會超時
此時我們需要將E降低
我們想下，是否存在一些邊是必選的，也就是不會受q的影響
限制的邊指的是被q選中的邊
我們將所有邊進行排序，第一順序為限制的邊在前，非限制的邊在后，第二順序是費用從小到大
然后跑一邊krusal，然后選到了n-1個邊(最小生成樹的邊)
我們設n-1個邊中限制邊的數量為x(0<=x<=32)，那么非限制邊就是y=n-1-x(n-1<=y<=n-33)。也就是說無論限制邊如何選擇，有y個非限制邊是一定會選擇的，那我們就將這個y個邊加入到最小生成樹中，記錄這y個邊權值。這樣就從原先n個點變成x+1個點未加入到最小生成樹中
雖然只剩下x+1個點，但是任意兩個點之間可能有很多邊，我們可以將其減少，使得每兩個點之間只有一個邊
我們將所有邊按照之前的排序方式再排，然后再跑一邊最小生成樹，將限定邊和可以加入最小生成樹的邊存下來，這樣得到新的邊集，數量為tot
此時的tot最大為64，完全可以跑過
詳細看代碼(注：不保證正確)

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug( a, b ) printf ( "%s = %d\n", a, b ); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; // Fe~Jozky const ll INF_ll = 1e18; const int INF_int = 0x3f3f3f3f; void read (){}; template <typename _Tp, typename... _Tps> void read ( _Tp &x, _Tps &...Ar ) {x = 0;char c = getchar ();bool flag = 0;while ( c < '0' || c > '9' )flag |= ( c == '-' ), c = getchar ();while ( c >= '0' && c <= '9' )x = ( x << 3 ) + ( x << 1 ) + ( c ^ 48 ), c = getchar ();if ( flag )x = -x;read ( Ar... ); } template <typename T> inline void write ( T x ) {if ( x < 0 ){x = ~( x - 1 );putchar ( '-' );}if ( x > 9 )write ( x / 10 );putchar ( x % 10 + '0' ); } void rd_test () {#ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen ( "in.txt", "r", stdin ); #endif } void Time_test () {#ifdef ONLINE_JUDGE #elseendTime = clock ();printf ( "\nRun Time:%lfs\n",(double)( endTime - startTime ) / CLOCKS_PER_SEC ); #endif } const int MAXM = 500005;struct Edge {int a, b, c, id; } edge[MAXM], tmp[MAXM]; ;int fa[MAXM]; void init ( int m, Edge *edge ) {for ( int i = 1; i <= m; i++ ){fa[edge[i].a] = edge[i].a;fa[edge[i].b] = edge[i].b;} } int find ( int x ) {return fa[x] == x ? x : fa[x] = find ( fa[x] ); } bool merge ( int x, int y ) {x = find ( x ), y = find ( y );if ( x == y )return 0;fa[x] = y;return 1; }int u[50], v[50]; bool key[MAXM], usd[MAXM]; /* 排序，第一順序為限制，非限制，第二順序為費用從小到大 跑一邊krusal得到n-1個邊 此時n-1個邊中的非限制邊是一定要選的 其中非限制邊的數量為x，n-1-32<=x<=n-1 我們將這n-1個邊中的非限制便直接選上然后將還可以加入最小生成樹的邊或者是限定選選出來，這是我們需要考慮的對這些邊排序，第一順序是非限制>限制，第二順序邊權<邊權*/ bool cmp ( Edge x, Edge y ) {return key[x.id] == key[y.id] ? x.c < y.c : key[x.id] > key[y.id]; } bool cmp1 ( Edge x, Edge y ) {return x.c < y.c; } int contraction ( int &n, int m, int &res ) {sort ( edge + 1, edge + m + 1, cmp );init ( m, edge );int tot = 0;for ( int i = 1; i <= m; i++ )if ( merge ( edge[i].a, edge[i].b ) )tmp[++tot] = edge[i];init ( tot, tmp );for ( int i = 1; i <= tot; i++ )if ( !key[tmp[i].id] ){merge ( tmp[i].a, tmp[i].b );n--;res += tmp[i].c;}tot = 0;for ( int i = 1; i <= m; i++ ){edge[i].a = find ( edge[i].a );edge[i].b = find ( edge[i].b );if ( key[edge[i].id] || edge[i].a != edge[i].b )edge[++tot] = edge[i];}return tot; } int removal ( int m ) //去掉重邊 {sort ( edge + 1, edge + m + 1, cmp );init ( m, edge );int tot = 0;for ( int i = 1; i <= m; i++ )if ( key[edge[i].id] || merge ( edge[i].a, edge[i].b ) )edge[++tot] = edge[i];return tot; } int main () {rd_test();int n, m;scanf ( "%d%d", &n, &m );for ( int i = 1; i <= m; i++ ){int a, b, c;scanf ( "%d%d%d", &a, &b, &c );edge[i] = Edge{ a, b, c, i };}int q;scanf ( "%d", &q );for ( int i = 0; i < q; i++ ){scanf ( "%d%d", &u[i], &v[i] );key[u[i]] = key[v[i]] = 1;}int base = 0, res = INF_int;int tmp = contraction ( n, m, base );printf("現在的邊有%d條\n",tmp);m = removal ( tmp );printf("現在的邊有%d條\n",m);sort ( edge + 1, edge + m + 1, cmp1 );for ( int state = 0; state < ( 1 << q ); state++ ){for ( int i = 0; i < q; i++ )usd[u[i]] = usd[v[i]] = 0;for ( int i = 0; i < q; i++ ){if ( state >> i & 1 )usd[u[i]] = 1;elseusd[v[i]] = 1;}init ( m, edge );int now = base, cnt = n;for ( int i = 1; i <= m; i++ )if ( usd[edge[i].id] ){if ( merge ( edge[i].a, edge[i].b ) )cnt--;now += edge[i].c;usd[edge[i].id] = 2;}for ( int i = 1; i <= m; i++ )if ( !usd[edge[i].id] && merge ( edge[i].a, edge[i].b ) )now += edge[i].c, cnt--;if ( cnt == 1 )res = min ( res, now );}printf ( "%d\n", ( res < INF_int ? res : -1 ) );return 0; }

總結

以上是生活随笔為你收集整理的2021银川Problem D. Farm(不保证正确性)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。