简答题 偏难
#21997

T2道路修复

T2道路修复

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int MAXN = 1e4 + 5; const int MAXM = 1e6 + 5; //快速读入  inline int read() {     int x=0,f=1;char ch=getchar();     while (ch&lt;'0'||ch&gt;'9'){if (ch=='-') f=-1;ch=getchar();}     while (ch&gt;='0'&amp;&amp;ch&lt;='9'){x=x*10+ch-48;ch=getchar();}     return x*f; } //边结构体 struct edge{     int u, v;     int w;  //边权 }; int n, m, k; vector&lt;edge&gt; OG;  //原图 vector&lt;edge&gt; NG;  //新图 int c[11];        //乡镇改造费用 int fa[MAXN+10];  //并查集 bool z[11];       //标记乡镇是否被选中 //按边权排序 bool cmp(edge x, edge y) { return x.w &lt; y.w; } // 标准并查集操作 int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); } void merge(int x, int y) {     x = findroot(x);     y = findroot(y);     fa[x] = y; } //第一次kruskal,用于求出s=0的答案,并删去m条边中后续不可能被选中的边 long long kruskal_first() {     for (int i = 1; i &lt;= n; i++) fa[i] = i;  //并查集初始化     long long res = 0;     int cnt = n - 1;  //需要选取n-1条     for (edge i : OG) {         if (!cnt) return res;  //选完就退出         int x = findroot(i.u), y = findroot(i.v);         if (x != y) {             merge(x, y);  //合并             cnt--;             res += i.w;             NG.push_back(i);  //将第一次MST选中的边加入新图         }     }     return res; } //加入乡镇后的MST long long kruskal(int s) {     for (int i = 1; i &lt;= n+k; i++) fa[i] = i;  //并查集初始化     memset(z, 0, sizeof z);  //标记数组初始化     long long res = 0;     int cnt = n - 1;     for (int i = 0, j = 1; i &lt; k; i++, j &lt;&lt;= 1) {         if (s &amp; j) {  //按二进制拆分状态             z[i] = 1;             res += c[i];             cnt++;         }     }     for (edge i : NG) {         if (!cnt) return res;         //如果边的连接点有乡镇,需要判断边是否存在         if ((i.u &gt; n &amp;&amp; !z[i.u-n-1]) || (i.v &gt; n &amp;&amp; !z[i.v-n-1])) continue;         int x = findroot(i.u), y = findroot(i.v);         if (x != y) {             merge(x, y);             cnt--;             res += i.w;         }     }     return res; } int main() {     int u, v, w;     n = read();     m = read();     k = read();     for (int i = 0; i &lt; m; i++) {         u = read();         v = read();         w = read();         OG.push_back({u, v, w});     }     //排序原图并进行第一次kruskal     sort(OG.begin(), OG.end(), cmp);     long long ans = kruskal_first();     //cout &lt;&lt; ans &lt;&lt; endl;     for (int j = 0; j &lt; k; j++) {         c[j] = read();         for (int i = 1; i &lt;= n; i++) {             w = read();             NG.push_back({n+j+1, i, w});         }     }     sort(NG.begin(), NG.end(), cmp);     int MAXK = 1 &lt;&lt; k;     //对于乡镇的所有选取状态进行kruskal     for (int s = 1; s &lt; MAXK; s++) ans = min(ans, kruskal(s));     printf("%lld", ans);     return 0; }</pre>
这道题暂未补解析。