Problem 4. airplane Input file: airplane.in Output file: airplane.out Time limit: 1 second cky 公司的运营蒸蒸日上，由于出差实在太频繁，而且坐汽车有些太慢了，所以cky 想要顺势直接进驻航空 业。cky 所在的国家天朝有n 个城市，m 个航空公司，每两个城市之间可能有一条航线运营（双向），一共 有k 条航线，每条航线都属于某一航空公司。现在cky 希望收购一家航空公司（为了涉足航空业以及防垄断， cky 必须且只能购买一家航空公司），使得他能通过飞机从任意城市到达目的城市（允许转机），当然很可能没 有一家公司能满足cky 的要求，所以cky 还需收购其他公司掌控的航线。每个航空公司都有一个市值，每条 航线都有一个收购价。现在cky 想知道他最少需要花费多少钱。 Input 第1 行，3 个整数n; m; k，表示城市数量，航空公司数和航线数。城市用1; 2; : : : ; n 编号。 接下来一行，一共m 个整数，第i 个整数ai 表示第i 个航空公司的市值。接下来k 行，每行4 个整数 ui; vi; costi; bi，表示第i 条航线连接城市u; v，价值costi，所属航空公司为bi 题目保证u! = v 题目保证有解。 Output 输出最少需要花费多少钱 Sample airplane.in airplane.out 4 3 3 100 150 200 1 2 100 1 1 3 160 2 1 4 220 3 460 Note • 对于50% 的数据，1 n 1000，1 m 1000，1 k 10000； • 对于100% 的数据，1 n 2000，1 m 2000，1 k 200000,1 bi m,1 costi; ai 108。
Airplane：最小生成树 最朴素的做法：枚举航空公司，将本公司的航线加入，然后做一遍MST，时间复杂度是O(klogk+mk)的。 但我们注意到“在最小生成树中任意一条边都是连接两个集合边权最小的一条边”，这个是MST一个非常重要的结论，是Prim和kruscal算法中贪心的核心。利用这条性质我们可以知道，对于每个航空公司，我们只需要原图MST中得到的航线即可得到最优购买方案。所以更优的做法是：先跑一次MST，把得到的边记录下来，然后枚举航空公司，还是先讲本公司的边全部加进去，然后只用扫一边第一次MST中记录下来的边，用kruscal的方法去构造树即可。时间复杂度为O(klogk+nm)。 对于本题，50%的数据是可以O(mk)过的，最后30%的数据我特别构造了一下,必须枚举到排序后的最后几条边才能构造出一颗生成树，所以O(mk)应该是过不了的，此外的20%数据是随机数据，加了构造出树就跳出判断的代码可能会过（但是jyb写的mk的没过。。）；另外，50%的数据需要long long
#include <cstdio> #include <algorithm> #define ll long long using namespace std; const int M = 200002; const int N = 2002; const ll INF = 1ll<<60; template <class T> inline void read(T &x) { int flag = 1; x = 0; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x<<1)+(x<<3)+ch-'0'; ch = getchar(); } x *= flag; } struct data { int u,v;ll w; bool operator < (const data &rhs) const {return w<rhs.w; } }dis[M],mst[N]; struct edges { int u,v,next; } edge[M]; int hu[N],num,fa[N],n,m,k,cnt,u,v,tmp,w; ll ans,a[N]; inline void addedge(int tmp, int u, int v) { edge[++num].u = u; edge[num].v = v; edge[num].next = hu[tmp]; hu[tmp] = num; } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } int main() { freopen("airplane.in","r",stdin); freopen("airplane.out","w",stdout); read(n), read(m), read(k); for(register int i = 1; i <= m; i++) read(a[i]); for(register int i = 1; i <= k; i++) { read(dis[i].u), read(dis[i].v), read(dis[i].w), read(tmp); addedge(tmp, dis[i].u, dis[i].v); } sort(dis+1, dis+1+k); for(register int i = 1; i <= n; i++) fa[i] = i; for(register int i = 1; i <= k; i++) { int x = find(dis[i].u), y = find(dis[i].v); if(x != y) fa[y] = x, mst[++cnt]=dis[i]; } ans = INF; for(register int i = 1; i <= m; i++) { for(register int j = 1; j <= n; j++) fa[j] = j; for(register int j = hu[i]; j; j = edge[j].next) { int x = find(edge[j].u), y = find(edge[j].v); if(x != y) fa[y] = x; } ll tot = 0; for(register int j = 1; j <= cnt; j++) { int x = find(mst[j].u), y = find(mst[j].v); if(x != y) fa[y] = x, tot += mst[j].w; } ans = min(ans, tot+a[i]); } printf("%I64d\n",ans); return 0; }