网站建设与管理简单么,wordpress更改底部,wordpress悬浮,昆明网站制作网页正题
题目链接:http://pjudge.ac/problem/21614 题目大意
给出一张nnn个点mmm条边的一张图#xff0c;有kkk个守卫#xff0c;每个守卫都有一个点集SSS表示这个守卫可以被派遣到这个点集中的某个点#xff0c;然后你可以选择一些边删除#xff0c;要求使得每个点都恰好和…正题
题目链接:http://pjudge.ac/problem/21614 题目大意
给出一张nnn个点mmm条边的一张图有kkk个守卫每个守卫都有一个点集SSS表示这个守卫可以被派遣到这个点集中的某个点然后你可以选择一些边删除要求使得每个点都恰好和一个守卫联通要求留下的边的权值和最小。
1≤n≤300,1≤m≤n×(n−1)21\leq n\leq 300,1\leq m\leq \frac{n\times (n-1)}{2}1≤n≤300,1≤m≤2n×(n−1) 解题思路
首先最后的所有边肯定都是最小生成树上的边我们可以先把最小生成树求出来。
然后我们考虑把最后有守卫的点集SSS拿出来建一棵虚树那么假设存在一条边x↔yx\leftrightarrow yx↔y那么原树x,yx,yx,y肯定不连通也就是x↔yx\leftrightarrow yx↔y路径上肯定有一条边会被删除。
显然我们删除路径上权值最大的边是最优的嗯考虑到这个最大的边我们可以建一个Kruskal生成树来更好的考虑。
那么对于一个边化成的点这条边如果产生贡献当且仅当它的两棵子树中都有点有守卫。
考虑使用费用流解决这个问题对于一个产生贡献的点如果左右两边都有流量上来它就会产生贡献并且会继承一个流量上去否则如果有一个流量就直接继承上去。
那么建法就很简单了对于这个点xxx建立x→tx\rightarrow tx→t流量111费用www。x→faxx\rightarrow fa_xx→fax流量111费用000。
并且对于每个根我们都建立x→tx\rightarrow tx→t流量111费用infinfinf并且在最后减去这些infinfinf即可。这样我们求一个最大费用最大流就是对的了。因为Kruskal生成树的原因深度越小的节点权值肯定越大所以两个流量肯定会在它们的LCALCALCA处产生贡献因为只能流一个上去。 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N1500,inf1e18;
struct node{ll x,y,w;
}e[N*N];
struct edge{ll to,next,w,c;
}a[N*20];
ll n,m,k,s,t,tot,ans,cnt,wr,fa[N];
ll ls[N],f[N],mf[N],pre[N];
bool v[N];queueint q;
bool cmp(node x,node y)
{return x.wy.w;}
ll find(ll x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
void addl(ll x,ll y,ll w,ll c){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].cc;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;a[tot].c-c;return;
}
bool SPFA(){memset(f,0xcf,sizeof(f));q.push(s);f[s]0;v[s]1;mf[s]inf;while(!q.empty()){ll xq.front();q.pop();v[x]0;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(a[i].wf[x]a[i].cf[y]){f[y]f[x]a[i].c;pre[y]i;mf[y]min(mf[x],a[i].w);if(!v[y])q.push(y),v[y]1;}}}return f[t]-inf;
}
void Update(){ansmf[t]*f[t];ll xt;wrmf[t];while(x!s){a[pre[x]].w-mf[t];a[pre[x]^1].wmf[t];xa[pre[x]^1].to;}return;
}
signed main()
{scanf(%lld%lld%lld,n,m,k);sn*2k1;ts1;tot1;for(ll i1;im;i)scanf(%lld%lld%lld,e[i].x,e[i].y,e[i].w);for(ll i1;in;i)fa[i]i;sort(e1,e1m,cmp);cntn;ll sum0;for(ll i1;im;i){ll xfind(e[i].x),yfind(e[i].y);if(xy)continue;fa[x]fa[y]cnt;fa[cnt]cnt;addl(x,cnt,1,0);addl(y,cnt,1,0);addl(cnt,t,1,e[i].w);sume[i].w;}for(ll i1;icnt;i)if(fa[i]i)addl(i,t,1,1e9),sum1e9;for(ll i1,r;ik;i){scanf(%lld,r);cnt;addl(s,cnt,1,0);for(ll j1,x;jr;j)scanf(%lld,x),addl(cnt,x,1,0);}while(SPFA())Update();sum-ans;if(sum1e9||wrk)return puts(-1)0;printf(%lld\n,sum);return 0;
}
