网站咋开通,域名 不做网站,建设网站要多少费用,wordpress添加豆列题目
题目链接
题解
很典型的最小割模型问题#xff0c;我们知道颜色不确定的点最终要么是白色#xff0c;要么是黑色#xff0c;是两种对立的状态#xff0c;我们联想到了最小割。 最小割是割掉权值和最小的边集#xff0c;使得图中的点分成两个点集#xff0c;一个…题目
题目链接
题解
很典型的最小割模型问题我们知道颜色不确定的点最终要么是白色要么是黑色是两种对立的状态我们联想到了最小割。 最小割是割掉权值和最小的边集使得图中的点分成两个点集一个包含sss点，一个包含t" role="presentation" style="position: relative;">ttt点与这道题的要求非常相似。
我们构建3组点。 一组是确定为白色的点与sss相连，流量为inf" role="presentation" style="position: relative;">infinfinf。 一组是确定为黑色的点与ttt相连，流量为inf" role="presentation" style="position: relative;">infinfinf。 一组是颜色不确定的点如果该点与白的的点之间有边那么就在该点与白色的点之间连接一条对应流量的边。如果与黑色的点有边相连类似。
这样的话跑一遍最小割/最大流被割掉的边就代表权值不能被取到的由于割是最小的所以剩下的是最大的。
代码
#include iostream
#include cstdio
#include vector
#include algorithm
using namespace std;
const int inf 1e9;
const int maxm 300001;
const int maxn 1001;
int node,src,dest,edge;
int ver[maxm],flow[maxm],nxt[maxm];
int head[maxn],work[maxn],dis[maxn],q[maxn];
void prepare(int _node,int _src,int _dest)
{node_node,src_src,dest_dest;for(int i0; inode; i)head[i]-1;edge0;
}
void add_edge(int u,int v,int c)
{ver[edge]v,flow[edge]c,nxt[edge]head[u],head[u]edge;ver[edge]u,flow[edge]0,nxt[edge]head[v],head[v]edge;
}
bool Dinic_bfs()
{int i,u,v,l,r0;for(i0; inode; i)dis[i]-1;dis[q[r]src]0;for(l0; lr; l)for(ihead[uq[l]]; i0; inxt[i])if(flow[i]dis[vver[i]]0){dis[q[r]v]dis[u]1;if(vdest)return 1;}return 0;
}
int Dinic_dfs(int u,int exp)
{if(udest)return exp;for(int iwork[u],v,tmp; i0; inxt[i])if(flow[i]dis[vver[i]]dis[u]1(tmpDinic_dfs(v,min(exp,flow[i])))0){flow[i]-tmp;flow[i^1]tmp;return tmp;}return 0;
}
int Dinic_flow()
{int i,ret0,delta;while(Dinic_bfs()){for(i0; inode; i)work[i]head[i];while(deltaDinic_dfs(src,inf))retdelta;}return ret;
}
typedef pairint,int pii;
vectorpii vec[100007];
int n,k,p,qq,tmp;
int kind[205];
int pkind[100007];
int G[205][205];
int ans;
int mxcut;
#define pr(x) cout#x:xendl
void dfs(int u,int fa){for(pii p : vec[u]){int v p.first,c p.second;int k1 kind[pkind[u]];int k2 kind[pkind[v]];if(u v) goto s;if(pkind[u] pkind[v]) {ans c;goto s;}if(k1 k2){if(k1 k2) ans c;}if(!k1 !k2){add_edge(pkind[u],pkind[v],c),mxcut c;}if(k1 !k2){if(k1 -1) add_edge(pkind[u],pkind[v],c),mxcut c;if(k1 1 ) add_edge(pkind[v],pkind[u],c),mxcut c;}if(!k1 k2){if(k2 -1) add_edge(pkind[v],pkind[u],c),mxcut c;if(k2 1 ) add_edge(pkind[u],pkind[v],c),mxcut c;}
s: if(v ! fa) dfs(v,u);}
}
int lp,rp;
int main(){scanf(%d %d %d %d,n,k,p,qq);for(int i 1;i p;i) scanf(%d,tmp),kind[tmp] - 1;for(int i 1;i qq;i) scanf(%d,tmp),kind[tmp] 1;for(int i 1;i n;i) scanf(%d,tmp),pkind[i] tmp;prepare(k2,0,k1);for(int i 1;i k;i) {if(kind[i] -1) add_edge(0,i,inf);if(kind[i] 1 ) add_edge(i,k1,inf);}for(int i 1;i n;i){int u,v,c;scanf(%d%d%d,u,v,c);vec[u].push_back(make_pair(v,c));vec[v].push_back(make_pair(u,c));}dfs(1,0);ans mxcut - Dinic_flow();coutansendl;
}
