榆社县济南网站建设公司 大学,影视小程序源码,网络平台推广引流,网站推广软文公司题目大意#xff1a; 给你一个无向图\(G(V,E)\)。 每个顶点都有一个int范围内的整数的标记。 不同的顶点可能有相同的标记。 对于边\((u,v)\)#xff0c;我们定义\(Cost(u,v)mark [u]\ \ xor\ \ mark [v]\)。 现在我们知道某些节点的标记了。你需要确定其他节点的标记#x…题目大意 给你一个无向图\(G(V,E)\)。 每个顶点都有一个int范围内的整数的标记。 不同的顶点可能有相同的标记。 对于边\((u,v)\)我们定义\(Cost(u,v)mark [u]\ \ xor\ \ mark [v]\)。 现在我们知道某些节点的标记了。你需要确定其他节点的标记以使边的总成本尽可能小。 最后要求输出的每个点的标号 QwQ一看到这种跟位运算有关题目就会想到按位来处理 仔细考虑发现这个题满足最小割的模型对于每一位当时将所有点的对应位分成0或者是1 那么我们按位来假设当前位是\(i\),对于已经知道编号的点\(x\)如果当前位是1的话我们\(insert(s,x,inf)\)否则\(insert(x,t,inf)\)表示这个点是0还是1同时inf的原因是给定的点的编号的不能改的 同时对于原图的边\(u-v\)我们只需要\(insert(u,v,1),insert(v,u,1)\) 表示这两个点的当前位是否相同最后跑\(dinic\)剩下的残余网络中与s相连且沿途流量\(0\)的就是1否则就是0 大致就是这样最后千万别忘记 1.编号可能是0 2.初始化数组 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includecmath
#includequeueusing namespace std;inline int read()
{int x0,f1;char chgetchar();while (!isdigit(ch)){if (ch-) f-1;chgetchar();}while (isdigit(ch)){x(x1)(x3)ch-0;chgetchar();}return x*f;
}const int maxn 1010;
const int maxm 200010;
const int inf 1e9;int point[maxn],nxt[maxm],to[maxm],val[maxm];
int h[maxn];
int num[maxn];
int ans[maxn];
int x[maxm],y[maxm];
int n,m,cnt1;
int s,t;
int vis[maxn];
queueint q;void addedge(int x,int y,int w){nxt[cnt]point[x];to[cnt]y;val[cnt]w;point[x]cnt;
}void init()
{cnt1;memset(point,0,sizeof(point));memset(vis,0,sizeof(vis));
}void insert(int x,int y,int w)
{addedge(x,y,w);addedge(y,x,0);
}bool bfs(int s)
{memset(h,-1,sizeof(h));h[s]0;q.push(s);while (!q.empty()){int x q.front();q.pop();for (int ipoint[x];i;inxt[i]){int p to[i];if (val[i]0 h[p]-1){h[p]h[x]1;q.push(p);}}}if (h[t]-1) return false;else return true;
}int dfs(int x,int low)
{if (xt || low0) return low;int totflow0;for (int ipoint[x];i;inxt[i]){int p to[i];if (val[i]0 h[p]h[x]1){int tmp dfs(p,min(val[i],low));val[i]-tmp;val[i^1]tmp;low-tmp;totflowtmp;if (low0) return totflow;}}if (low0) h[x]-1;return totflow;
}int dinic(){int ans0;while (bfs(s)){ansdfs(s,inf);}
}void dfs1(int x,int d)
{vis[x]1;ans[x]|(1 d); for (int ipoint[x];i;inxt[i]){int p to[i];if (!vis[p] val[i]0){dfs1(p,d);}}
}
void build(int xx)
{init();sn10;ts1; for (int i1;in;i){if (num[i]!-1){if (num[i] (1xx)) insert(s,i,inf);else insert(i,t,inf);}}for (int i1;im;i){insert(x[i],y[i],1);insert(y[i],x[i],1);}dinic();dfs1(s,xx);
}int T;
int main()
{scanf(%d,T);while (T--){memset(num,-1,sizeof(num));memset(ans,0,sizeof(ans));init();nread(),mread();for (int i1;im;i) x[i]read(),y[i]read();int k;kread();for (int i1;ik;i){int oo;ooread();num[oo]read();}for (int i0;i32;i){build(i);}for (int i1;in;i) printf(%d\n,ans[i]);}return 0;
}转载于:https://www.cnblogs.com/yimmortal/p/10160835.html
