「BZOJ2400」SPOJ 839 Optimal Marks

2014年12月27日5,7312

Description

定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。

定义一个无向图的值为：这个无向图所有边的值的和。

给你一个有n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。

Input

第一行，两个数n，m，表示图的点数和边数。

接下来n行，每行一个数，按编号给出每个点的值（若为负数则表示这个点的值由你决定，值的绝对值大小不超过10^9）。

接下来m行，每行二个数a，b，表示编号为a与b的两点间连一条边。（保证无重边与自环。）

Output

第一行，一个数，表示无向图的值。

第二行，一个数，表示无向图中所有点的值的和。

Sample Input

3 2
2
-1
0
1 2
2 3

Sample Output

2
2

HINT

数据约定
n<=500，m<=2000
样例解释
2结点的值定为0即可。

题解

考虑用最小割解决问题，考虑二进制每一位

设残量网络中S可到达的点为0，可到达T的点为1

显然S到确定为0的点连inf，确定为1的点向T连inf

然后再建给出的无向边。。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define inf 1000000000 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans1,ans2;
int bin[35];
int n,m,cnt,T;
int a[505],u[2005],v[2005],val[505];
int h[505],q[505],cur[505],last[505];
bool mark[505];
struct edge{
    int to,next,v;
}e[200005];
void insert(int u,int v,int w)
{
//	cout<<u<<' '<<v<<' '<<w<<endl;
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
void dfs(int x)
{
	mark[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i^1].v&&!mark[e[i].to])dfs(e[i].to);
}
bool bfs()
{
    int head=0,tail=1;
    for(int i=0;i<=T;i++)h[i]=-1;
    q[0]=0;h[0]=0;
    while(head!=tail)
    {
        int now=q[head];head++;
        for(int i=last[now];i;i=e[i].next)
            if(h[e[i].to]==-1&&e[i].v)
            {
                h[e[i].to]=h[now]+1;
                q[tail++]=e[i].to;
            }
    }
    return h[T]!=-1;
}
int dfs(int x,int f)
{
    if(x==T)return f;
    int w,used=0;
    for(int i=cur[x];i;i=e[i].next)
        if(h[e[i].to]==h[x]+1)
        {
            w=dfs(e[i].to,min(e[i].v,f-used));
            e[i].v-=w;e[i^1].v+=w;
            if(e[i].v)cur[x]=i;
            used+=w;if(used==f)return f;
        }
    if(!used)h[x]=-1;
    return used;
}
int dinic()
{
	int tmp=0;
    while(bfs())
    {
        for(int i=0;i<=T;i++)
            cur[i]=last[i];
        tmp+=dfs(0,inf);
    }
	return tmp;
}
void build(int x)
{
//	cout<<endl;
	cnt=1;T=n+1;
	memset(last,0,sizeof(last));
	for(int i=1;i<=n;i++)
		if(a[i]>=0)
		{
			if(a[i]&x)insert(i,T,inf);
			else insert(0,i,inf);
		}
	for(int i=1;i<=m;i++)
	{
		insert(u[i],v[i],1);
		insert(v[i],u[i],1);
	}
}
int main()
{
	bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;
	n=read();m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++)
		u[i]=read(),v[i]=read();
	for(int i=0;i<=30;i++)
	{
		build(bin[i]);
		ans1+=(ll)bin[i]*dinic();
		memset(mark,0,sizeof(mark));
		dfs(T);
		for(int j=1;j<=n;j++)
		{
			if(mark[j])val[j]+=bin[i];
		}
	}
	printf("%I64d\n",ans1);
	for(int i=1;i<=n;i++)
		if(a[i]>0)ans2+=a[i];
		else ans2+=val[i];
	printf("%I64d\n",ans2);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans1,ans2;

int bin[35];

int n,m,cnt,T;

int a[505],u[2005],v[2005],val[505];

int h[505],q[505],cur[505],last[505];

bool mark[505];

struct edge{

int to,next,v;

}e[200005];

void insert(int u,int v,int w)

{

// cout<<u<<' '<<v<<' '<<w<<endl;

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;

}

void dfs(int x)

{

mark[x]=1;

for(int i=last[x];i;i=e[i].next)

if(e[i^1].v&&!mark[e[i].to])dfs(e[i].to);

}

bool bfs()

{

int head=0,tail=1;

for(int i=0;i<=T;i++)h[i]=-1;

q[0]=0;h[0]=0;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(h[e[i].to]==-1&&e[i].v)

{

h[e[i].to]=h[now]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=cur[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=dfs(e[i].to,min(e[i].v,f-used));

e[i].v-=w;e[i^1].v+=w;

if(e[i].v)cur[x]=i;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

int dinic()

{

int tmp=0;

while(bfs())

{

for(int i=0;i<=T;i++)

cur[i]=last[i];

tmp+=dfs(0,inf);

}

return tmp;

}

void build(int x)

{

// cout<<endl;

cnt=1;T=n+1;

memset(last,0,sizeof(last));

for(int i=1;i<=n;i++)

if(a[i]>=0)

{

if(a[i]&x)insert(i,T,inf);

else insert(0,i,inf);

}

for(int i=1;i<=m;i++)

{

insert(u[i],v[i],1);

insert(v[i],u[i],1);

}

int main()

{

bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;

n=read();m=read();

for(int i=1;i<=n;i++)

a[i]=read();

for(int i=1;i<=m;i++)

u[i]=read(),v[i]=read();

for(int i=0;i<=30;i++)

{

build(bin[i]);

ans1+=(ll)bin[i]*dinic();

memset(mark,0,sizeof(mark));

dfs(T);

for(int j=1;j<=n;j++)

{

if(mark[j])val[j]+=bin[i];

}

printf("%I64d\n",ans1);

for(int i=1;i<=n;i++)

if(a[i]>0)ans2+=a[i];

else ans2+=val[i];

printf("%I64d\n",ans2);

return 0;

}

« 「泉七培训 – 杨国烨」图「BZOJ2229」[ZJOI2011] 最小割 »

婷小葵葵葵

这样做有没有可能最后的值大于1e9？

hzwer

有可能~

hzwer.com _ Home | http://hzwer.com

「BZOJ2400」SPOJ 839 Optimal Marks

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论