【算法】最小生成树
【题解】
想到网络流，但是好像不能处理流量和费用的关系。
想到最短路，但好像不能处理重复选边的问题。
每条边只需要选一次，每个点就要遍历到，可以想到最小生成树。
建超级源向每个点连边，点与点连边，对n+1个点求最小生成树(MST)即可。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=310; int n,first[maxn],tot,fa[maxn]; struct edge{int u,v,w,from;}e[maxn*maxn*3]; void insert(int u,int v,int w) {tot++;e[tot].u=u;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;} int getfa(int x){return fa[x]==x?x:(fa[x]=getfa(fa[x]));} bool cmp(edge a,edge b) {return a.w<b.w;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int u; scanf("%d",&u); insert(0,i,u); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int u; scanf("%d",&u); insert(i,j,u); } } for(int i=1;i<=n;i++)fa[i]=i; sort(e+1,e+tot+1,cmp); int cnt=0,ans=0; for(int i=1;i<=tot;i++) if(getfa(e[i].u)!=getfa(e[i].v)) { cnt++;fa[fa[e[i].u]]=fa[e[i].v]; ans+=e[i].w; if(cnt>=n)break; } printf("%d",ans); return 0; }