此题Amber的论文上还是有讲,建图的方法就不再赘述
题意描述:一个无向图,一些顶点权值已知而一些顶点权值未知,其中图中边的权值为其关联的两个顶点的异或值,现在让你在未知权值的顶点上填上权值后使得要求所有的边权之和最小,输出每个顶点的权值
关键是怎样输出方案。
我们按位进行网络流时,只需要到已知的最大标号的最大的一位即可。
然后对每一位做完最大流后,还是dfs残留网络,找不满流的边能到达的所有点即可。这能保证S集合中的个数最少。即保证了有多个方案下标号和最小的方案
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 555
#define MAXM 55555
#define INF 100000007
using namespace std;
typedef int type;
struct node
{
int v;
type c, f;
int next, r;
}edge[MAXM];
int dist[MAXN], nm[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, type c)
{
edge[e].v = y;
edge[e].c = c;
edge[e].f = 0;
edge[e].r = e + 1;
edge[e].next = head[x];
head[x] = e++;
edge[e].v = x;
edge[e].c = 0;
edge[e].f = 0;
edge[e].r = e - 1;
edge[e].next = head[y];
head[y] = e++;
}
void rev_BFS()
{
int Q[MAXN], h = 0, t = 0;
for(int i = 1; i <= n; ++i)
{
dist[i] = MAXN;
nm[i] = 0;
}
Q[t++] = des;
dist[des] = 0;
nm[0] = 1;
while(h != t)
{
int v = Q[h++];
for(int i = head[v]; i != -1; i = edge[i].next)
{
if(edge[edge[i].r].c == 0 || dist[edge[i].v] < MAXN)continue;
dist[edge[i].v] = dist[v] + 1;
++nm[dist[edge[i].v]];
Q[t++] = edge[i].v;
}
}
}
void init()
{
e = 0;
memset(head, -1, sizeof(head));
}
type maxflow()
{
rev_BFS();
int u;
type total = 0;
int cur[MAXN], rpath[MAXN];
for(int i = 1; i <= n; ++i)cur[i] = head[i];
u = src;
while(dist[src] < n)
{
if(u == des) // find an augmenting path
{
type tf = INF;
for(int i = src; i != des; i = edge[cur[i]].v)
tf = min(tf, edge[cur[i]].c);
for(int i = src; i != des; i = edge[cur[i]].v)
{
edge[cur[i]].c -= tf;
edge[edge[cur[i]].r].c += tf;
edge[cur[i]].f += tf;
edge[edge[cur[i]].r].f -= tf;
}
total += tf;
u = src;
}
int i;
for(i = cur[u]; i != -1; i = edge[i].next)
if(edge[i].c > 0 && dist[u] == dist[edge[i].v] + 1)break;
if(i != -1) // find an admissible arc, then Advance
{
cur[u] = i;
rpath[edge[i].v] = edge[i].r;
u = edge[i].v;
}
else // no admissible arc, then relabel this vtex
{
if(0 == (--nm[dist[u]]))break; // GAP cut, Important!
cur[u] = head[u];
int mindist = n;
for(int j = head[u]; j != -1; j = edge[j].next)
if(edge[j].c > 0)mindist = min(mindist, dist[edge[j].v]);
dist[u] = mindist + 1;
++nm[dist[u]];
if(u != src)
u = edge[rpath[u]].v; // Backtrack
}
}
return total;
}
int nt, m, xx[MAXM], yy[MAXM], num[MAXN], k;
int ans[MAXN], vis[MAXN], base;
void dfs(int u)
{
vis[u] = 1;
ans[u] += base;
for(int i = head[u]; i != -1; i = edge[i].next)
if(edge[i].c && !vis[edge[i].v])
dfs(edge[i].v);
}
int main()
{
int T, u, w;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &nt, &m);
n = nt + 2;
src = nt + 1;
des = nt + 2;
for(int i = 1; i <= m; i++) scanf("%d%d", &xx[i], &yy[i]);
scanf("%d", &k);
int mx = 0;
memset(num, -1, sizeof(num));
for(int i = 1; i <= k; i++)
{
scanf("%d%d", &u, &w);
num[u] = w;
mx = max(mx, w);
}
memset(ans, 0, sizeof(ans));
base = 1;
while(mx)
{
init();
for(int i = 1; i <= m; i++) add(xx[i], yy[i], 1), add(yy[i], xx[i], 1);
for(int i = 1; i <= nt; i++)
{
if(num[i] == -1) continue;
if(num[i] & 1) add(src, i, INF);
else add(i, des, INF);
num[i] >>= 1;
}
maxflow();
memset(vis, 0, sizeof(vis));
dfs(src);
base *= 2;
mx >>= 1;
}
for(int i = 1; i <= nt; i++)
printf("%d\n", ans[i]);
}
return 0;
}
分享到:
相关推荐
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 ...
Online Judge Problem solution VN.SPOJ
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ-Solutions:SPOJ算法问题的解决方案
My solution for some spoj problems
SPOJ( )上选定问题的解决方案
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
联系 Python中SPOJ问题的解决方案。
分机检查spoj用户的排名。 此扩展名有2个选项: - 在选择的比赛中显示用户排名 - 在选择比赛中最多可比较5个用户第一个在后台运行,并在每隔几分钟内更新,您可以设置自己(并默认为15分钟)。当您单击分机的徽标时...
检查SPOJ用户等级的扩展名。 这个扩展有两个选项: - 在选择比赛中显示用户等级 - 比较最多5个用户选择比赛 第一个在后台运行,每隔几分钟更新一次,您可以自己设置(默认为15分钟)。 第二个是当你点击分机的标志...
gcd(a,b)= d (d为素数,1,1)
spoj MSTS kruskal +生成树
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
cp:一些SPOJ问题的解决方案
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...