限制某个顶点度数的最小生成树 poj1639
Time Limit: 5000MS | Memory Limit: 10000K | |
Total Submissions: 10642 | Accepted: 3862 |
Description
Input
Output
Total miles driven: xxx
where xxx is the total number of miles driven by all the brothers' cars.
Sample Input
10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3
Sample Output
Total miles driven: 183 以下内容均为转载(代码风格也没改,就是这么懒=_=)http://www.cnblogs.com/jackge/archive/2013/05/12/3073669.html 膜
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<climits>
#include<queue>
using namespace std;
const int N=30;
struct node{
int v,cap;
node(){}
node(int _v,int _cap):v(_v),cap(_cap){}
bool operator < (const node &a) const{
return a.cap<cap;
}
};
map<string,int> mp;
int g[N][N],dis[N],clo[N],pre[N],fst[N],max_side[N];
int n,m,k;
int Prim(int src,int id){
priority_queue<node> q;
while(!q.empty())
q.pop();
dis[src]=0;
q.push(node(src,0));
int ans=0;
while(!q.empty()){
node cur=q.top();
q.pop();
int u=cur.v;
if(!clo[u]){
clo[u]=id;
ans+=dis[u];
for(int i=1;i<n;i++)
if(!clo[i] && g[u][i]!=0 && dis[i]>g[u][i]){ //满足松弛条件
pre[i]=u;
dis[i]=g[u][i];
q.push(node(i,dis[i]));
}
}
}
return ans;
}
void update(int cur,int last,int maxside){ //也是一个dfs过程,直到搜回到起点,同时完成了max_side[]更新
max_side[cur]=maxside>g[cur][last]?maxside:g[cur][last];
for(int i=1;i<n;i++)
if(i!=last && g[cur][i]!=0 && (pre[cur]==i || pre[i]==cur))
update(i,cur,max_side[cur]);
}
void Solve(){
int i,res,cnt;
for(i=0;i<n;i++){
dis[i]=INT_MAX;
clo[i]=pre[i]=fst[i]=0;
}
res=0,cnt=1; //除去根节点后,图中的连通子图个数,即最小生成树个数
for(i=1;i<n;i++)
if(!clo[i])
res+=Prim(i,cnt++);
for(i=1;i<n;i++){ //找到每个生成树和 Park 最近的点使之和 Park 相连
int id=clo[i];
if(g[0][i]!=0 && (!fst[id] || g[0][i]<g[0][fst[id]]))
fst[id]=i;
}
for(i=1;i<cnt;i++){ //把m个生成树上和根节点相连的边加入res,得到关于Park的最小m度生成树
res+=g[0][fst[i]];
g[0][fst[i]]=g[fst[i]][0]=0; //之所以用邻接阵就是因为删除边很方便
update(fst[i],0,0);
}
/*
添删操作:将根节点和生成树中一个点相连,会产生一个环,将这个环上(除刚添的那条边外)权值最大
的边删去.由于每次操作都会给总权值带来影响 d=max_side[tmp]-mat[0][tmp],我们需要得到最小生
成树,所以我们就要求 d 尽量大
*/
k=k-cnt+1; //接下来重复操作,直到度数满足条件
while(k--){
int tmp=0;
for(i=1;i<n;i++) //找 d 值最大的点(就是说完成添删操作后可以使总边权减小的值最大)
if(g[0][i]!=0 && (tmp==0 || max_side[tmp]-g[0][tmp]<max_side[i]-g[0][i]))
tmp=i;
if(max_side[tmp]<=g[0][tmp]) //总权值无法再减小
break;
res=res-max_side[tmp]+g[0][tmp];
g[0][tmp]=g[tmp][0]=0;
int p=0;
for(i=tmp;pre[i]!=0;i=pre[i])
if(p==0 || g[p][pre[p]]<g[i][pre[i]])
p=i;
pre[p]=0;
update(tmp,0,0);
}
printf("Total miles driven: %d\n",res);
}
int main(){
//freopen("input.txt","r",stdin);
char s1[20],s2[20];
int cap;
while(~scanf("%d",&m)){
mp["Park"]=0;
n=1;
memset(g,0,sizeof(g));
while(m--){
scanf("%s %s %d",s1,s2,&cap);
if(!mp.count(s1))
mp[s1]=n++;
if(!mp.count(s2))
mp[s2]=n++;
int u=mp[s1],v=mp[s2];
if(!g[u][v] || g[u][v]>cap)
g[u][v]=g[v][u]=cap;
}
scanf("%d",&k);
Solve();
}
return 0;
}
由于一直觉得上一份有点错误 ,所以又找了一份,发现这两个思想一样啊 =_=还是觉得有点错误,先挖坑以后来填
#include <cstdio>
#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1111;
int n,k;
map<string,int> name;
vector<string> vec;
int g[N][N],vis[N];
int li[N][N],lowcost[N],pre[N];
int kk,ans;
struct node{
int u,v,len;
node(){}
node(int _u,int _v,int _del):u(_u),v(_v),len(_del){}
}del[N];
void prim(int u){
for(int i = 1;i < n;i++){
lowcost[i] = g[u][i];
pre[i] = u;
}
vis[u] = true;
while(true){
int pr = -1 , mind = inf;
for(int i = 1;i < n;i++)
if(!vis[i] && lowcost[i] < mind){
mind = lowcost[i];
pr = i;
}
if(pr == -1) break;
ans += mind;
li[pre[pr]][pr] = li[pr][pre[pr]] = 1;
if(g[0][kk] > g[0][pr]) kk = pr;
vis[pr] = true;
for(int i = 1;i < n;i++)
if(!vis[i] && lowcost[i] > g[pr][i])
lowcost[i] = g[pr][i] , pre[i] = pr;
}
}
void dfs(int u,int fa,int del_u,int del_v){
for(int i = 1;i < n;i++){
if(li[u][i] && i!=fa){
if(fa == -1 || g[del_u][del_v] < g[u][i]){
del[i] = node(u,i,g[u][i]);
dfs(i,u,u,i);
}else{
del[i] = node(del_u,del_v,g[del_u][del_v]);
dfs(i,u,del_u,del_v);
}
}
}
}
void solve(){
memset(vis,0,sizeof(vis));
memset(li,0,sizeof(li));
ans = 0;
vis[0] = true;
for(int i = 1;i < n;i++){
if(vis[i]) continue;
kk = i;
k--;
prim(i);
li[0][kk] = li[kk][0] = 1;
ans += g[0][kk];
dfs(kk,-1,-1,-1);
}
memset(vis,0,sizeof(vis));
while(k--){
int c = 0 , todel = -1;
for(int i = 1;i < n;i++){
if(li[0][i] || g[0][i] == inf) continue;
if(c > g[0][i] - del[i].len){
c = g[0][i] - del[i].len;
todel = i;
}
}
if(c == 0) break;
ans += c;
li[0][todel] = li[todel][0] = 1;
li[del[todel].u][del[todel].v]=li[del[todel].v][del[todel].u] = 0;
dfs(todel, 0 , -1,-1);
}
printf("Total miles driven: %d\n",ans);
}
int getNum(const string &s){
if(name.count(s) > 0)
return name[s];
vec.push_back(s);
return name[s] = vec.size()-1;
}
void init(){
memset(g,0x3f,sizeof(g));
name.clear();
vec.clear();
getNum("Park");
string su,sv;
for(int i = 0,w;i < n;i++){
cin >> su >> sv;
cin >> w;
int u = getNum(su) ,v = getNum(sv);
if(g[u][v] > w)
g[u][v] = g[v][u] = w;
}
n = vec.size();
scanf("%d",&k);
}
int main(){
while(scanf("%d",&n)!=EOF){
init();
solve();
}
return 0;
}
最新文章
- centos6安装python3.4和pip3
- Axure 7.0 正式版 + 汉化包 安装
- Lock读写锁技术的妙用
- --------------------------PHP中访问数据库时带来的响应速度的问题解决-------------------------------------
- 147. Insertion Sort List
- SQLite数据库的基本API函数
- Android用户界面 UI组件--TextView及其子类(一) TextView
- js substr()与substring()的区别
- mysql水平分表和垂直分表的优缺点
- java知识点总结--java数据类型
- Linux CFS调度器之队列操作--Linux进程的管理与调度(二十七)
- Nowcoder | [题解-N210]牛客OI月赛2-提高组
- JAVA:IDEA使用Hibernate(2)
- shell 命令 if elif else fi 用法
- 并查集——合作网络D306
- 58-63用ssh远程连接linux系统
- Mac OS X 下搭建thrift环境
- dijkstra算法计算最短路径和并输出最短路径
- Java DecimalFormat的主要功能及使用方法
- learning shell args handing key=value example (2)