题目链接
题解
直接套用网络流炒鸡源点的想法建立一个炒鸡水库.
然后城镇之间正常连边，城与水库之间连对应花费
跑一边kruskal求出最小生成树的总花费就是题目所求辣.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; } #define maxn 100001 int ecnt,n; int head[maxn],f[maxn]; struct edge{ int u,v,w,next; bool operator<(const edge &rhs)const{ return w<rhs.w; } }E[maxn<<1];// void addedge(int u,int v,int w){ E[++ecnt].u=u; E[ecnt].v=v; E[ecnt].w=w; E[ecnt].next=head[u]; head[u]=ecnt; } int getf(int x){ return f[x]==x?x:f[x]=getf(f[x]); } int kruskal(){ sort(E+1,E+n*n+1); int v=0;int cnt=0; for(int i=1;i<=n*n;i++){ int u=getf(E[i].u);int vv=getf(E[i].v); if(u!=vv){ f[vv]=u;v+=E[i].w; //printf("%d %d %d\n",E[i].u,E[i].v,E[i].w); if(++cnt==n) return v; } } return 0; } int main() { //freopen("a.in","r",stdin); read(n);f[n+1]=n+1; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=n;i++){ int w;read(w); addedge(n+1,i,w); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ int w;read(w); if(i!=j) addedge(i,j,w); } printf("%d\n",kruskal()); return 0 ; } |
By:Wahacer
2018.3.3
12:26