注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3559][Ctsc2014]图的分割  

2015-05-18 10:53:01|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3559: [Ctsc2014]图的分割

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 36  Solved: 21
[Submit][Status][Discuss]

Description

Input

 输入的第一行包含两个正整数n,m,表示输入的无向图有n个顶点,m条无向边。
第二行包含两个正整数Z[1],Z[2],...,Z[n](Z[i]≤10^9)。
下面m行,每行三个正整数u,v,w(1≤u,v≤n,u≠v,w≤10^9),表示图中存在一条边(u,v)且权值为w。输入的无向图保证没有重边和自环。

Output

输出包含k+1行,第一行包含一个正整数k,表示你给出的分割的度。
下面k行,每行描述一个C。每行一开始包含一个正整数t,表示|Ci|,然后跟着t个不超过n的正整数,表示C中的顶点编号。

Sample Input

5 6 3 3 2 2 1 1 2 3 1 3 5 1 4 6 2 4 10 2 5 5 4 5 8

Sample Output

4 2 1 2 1 3 1 4 1 5

HINT

对于10%的数据,满足n=2
对于30%的数据,满足n≤10
对于60%的数据,满足n≤500,m≤2000
对于100%的数据,满足n≤100000,m≤500000

Solution

各个函数的意义:

S(G):边权>=MST上的最大边边权的边

D(Ci,Cj):连接点集Ci,Cj的最小边

M(C):把C拿去做MST,C中最大的边权

 

一个构造算法是:将所有边从小到大排序,类似Kruskal算法,每次判断待加入的边(u,v)是否满足w(u,v)≤min(M(C1)+Z[|C1|], M(C2)+Z[|C2|]),其中C1,C2为边(u,v)当前分别所属的连通块。

如果某次某条边没有被加入,可以说明C1,C2中满足min的那个连通块,在之后权值也不会改变。由此可以说明这样得到的分割是半完美的。

如果在这个方案中,分割中的某个连通块可以被半完美分割,考虑这个分割中横跨不同块的权值最小的边,执行之前的算法到这条边时,两边的连通块是不满足可以沿这条边切开的,考虑到之后的边权会更大,不难看出之后也不可能沿着这条边切开。

Code

/**************************************************************
    Problem: 3559
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:860 ms
    Memory:10216 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#define N 100010
int n,m,et,la[N],cnt,fa[N],siz[N],z[N],i,x,y,val[N],col[N],t,s[N];
struct E{int to,nxt;}e[N];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
struct D{int x,y,v;}d[500010];
bool operator<(const D&a,const D&b){return a.v<b.v;}
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
#define min(a,b) (a<b?a:b)
int main(){
    for(n=F(),m=F(),i=1;i<=n;i++)z[i]=F(),fa[i]=i,val[i]=z[1],siz[i]=1;
    for(i=1;i<=m;i++)d[i]=(D){F(),F(),F()};
    for(std::sort(d+1,d+1+m),i=1;i<=m;i++)
    if(x=gf(d[i].x),y=gf(d[i].y),x!=y&&d[i].v<=min(val[x],val[y]))
    fa[x]=y,siz[y]+=siz[x],val[y]=d[i].v+z[siz[y]];
    for(i=n;i;i--)if(gf(i),add(fa[i],i),fa[i]==i)col[++cnt]=i;
    for(printf("%d\n",cnt);cnt;cnt--,puts("")){
        for(t=0,i=la[col[cnt]];i;i=e[i].nxt)s[++t]=e[i].to;
        for(printf("%d",t),i=1;i<=t;printf(" %d",s[i++]));
    }
}
  评论这张
 
阅读(141)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018