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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 584(最小树形图)  

2013-08-03 09:40:30|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目挺简单的一次。。但是最后一题是道最小树形图(虽然可以状压啦)
所以贴个代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=100000+10;
const int INF=100000000;

int n;

struct Edge
{
int u,v;
int w;
Edge(int a,int b,int c):u(a),v(b),w(c){}
Edge(){}
}e[MAX];
int nume,Root,in[MAX],come[MAX],cc[MAX],q[MAX];
int Hash[MAX],lab[MAX],cnt;

int MST(int Root,int V,int E)
{
int i;
int ans=0;
while(1)
{
REP(i,1,V)
{
in[i]=INF;
cc[i]=0;
come[i]=0;
}
REP(i,1,E)
{
int s=e[i].u;
int t=e[i].v;
int c=e[i].w;
if(t!=Root && s!=t && c<in[t])
{
in[t]=c;
come[t]=s;
}
}
REP(i,1,V)
if(come[i])
++cc[come[i]];
REP(i,1,V)
if(i!=Root)
{
if(in[i]==INF)
return -1;
ans+=in[i];
}
int first(0),last(0);
REP(i,1,V)
if(cc[i]==0)
q[last++]=i;
while(first<last)
{
int u=q[first++];
int v=come[u];
if(v)
{
--cc[v];
if(!cc[v])
q[last++]=v;
}
}
cnt=0;
fill(Hash+1,Hash+V+1,0);
fill(lab+1,lab+V+1,0);
REP(i,1,V)
{
if(!cc[i] || lab[i])
continue;
int u=i;
while(Hash[u]!=i && !lab[u] && u!=Root)
{
Hash[u]=i;
u=come[u];
}
if(u!=Root && !lab[u])
{
lab[i]=++cnt;
for(int u=come[i];u!=i;u=come[u])
lab[u]=cnt;
}
}
if(!cnt)
break;
REP(i,1,V)
if(!lab[i])
lab[i]=++cnt;
REP(i,1,E)
{
int s=e[i].u;
int t=e[i].v;
e[i].u=lab[s];
e[i].v=lab[t];
if(lab[s]==lab[t])
continue;
e[i].w-=in[t];
}
V=cnt;
Root=lab[Root];
}
return ans;
}

struct FoxTheLinguist
{
void Read(string all)
{
int i;
int Len=all.size();
for(i=0;i<Len;i+=12)
{
int s=(all[i+0]-'A')*10+(all[i+1]-'0');
int t=(all[i+4]-'A')*10+(all[i+5]-'0');
int Time=all[i+7]-'0';
Time=Time*10+all[i+8]-'0';
Time=Time*10+all[i+9]-'0';
Time=Time*10+all[i+10]-'0';
++s;
++t;
e[++nume]=Edge(s,t,Time);
}
}
int minimalHours(int n, vector <string> courseInfo)
{
int i,j;
string all;
REP2(i,0,(int)courseInfo.size())
all+=courseInfo[i];
Read(all);

Root=n*10+1;
REP(i,1,n)
e[++nume]=Edge(Root,(i-1)*10+1,0);
REP(i,1,n)
REP(j,2,10)
e[++nume]=Edge((i-1)*10+j,(i-1)*10+j-1,0);

return MST(Root,Root,nume);
}
};



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

历史上的今天

评论

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

页脚

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