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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU323 水过  

2012-08-15 21:07:11|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很好的一道题,只可惜暴力加基础剪枝即可AC,暂且放过mk暴力不提,其实本题是可以做到klogn的
首先求出最小生成树,接下来枚举m,将m的所有边边权设为0,发现最小生成树上的边是没有影响的,树外的边则应加入最小生成树,方式很简单,将环上最大的边删去即可。这便是动态最小生成树问题,用LCT维护即可
不过我终究还是太弱了,不敢尝试
于是暴力了事

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;

const int INF=1000000000;
const int MAX=200000+10;
const int NUM=3000;

int n,m,k,fa[NUM],best(INF),bestm,num,ans;
vector<int> t[NUM],st[NUM];

struct Edge
{
int a,b,c,d,num;
}e[MAX];
int change[MAX];

int cmp(const Edge& a,const Edge& b)
{
return a.d<b.d;
}

int findfather(int u)
{
return fa[u]==u?u:fa[u]=findfather(fa[u]);
}

void work(int c,int j)
{
if(findfather(e[j].a)==findfather(e[j].b))
return;
--num;
ans+=e[j].d * (e[j].c!=c);
if(e[j].c!=c)st[c].push_back(j);
fa[findfather(e[j].a)]=findfather(e[j].b);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
scanf("%d %d %d",&n,&m,&k);
int i,l;
size_t j;
for(i=1;i<=k;++i)
{
scanf("%d %d %d %d",&e[i].a,&e[i].b,&e[i].c,&e[i].d);
e[i].num=i;
}
sort(e+1,e+k+1,cmp);
for(i=1;i<=k;++i)
t[e[i].c].push_back(i);
for(i=1;i<=m;++i)
{
for(l=1;l<=n;++l)fa[l]=l;
num=n;ans=0;
for(j=0;j<t[i].size() && num>1 ;++j)
work(i,t[i][j]);
for(l=1;l<=k && ans<best && num>1 ;++l)
if(e[l].c!=i)work(i,l);
if(ans<best && num==1)
best=ans,bestm=i;
}
printf("%d %d %d\n",best,bestm,st[bestm].size());
for(j=0;j<st[bestm].size();++j)
printf("%d ",e[st[bestm][j]].num);
return 0;
}



  评论这张
 
阅读(202)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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