| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1365 人关注过本帖
标题:一道dfs的题,不会优化,求教怎么优化
只看楼主 加入收藏
莫名Vet
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2017-3-6
结帖率:100%
收藏
已结贴  问题点数:61 回复次数:4 
一道dfs的题,不会优化,求教怎么优化
Long time ago, there were n cities in a country named ABP(A Beautiful Place).
There was an interconnected network of trade routes among some of the cities. Realized that a powerful nation was based on good connection among the cities, the King of the country make a decision to set up a freeway network, which is also known as the Silk Road Project. The king selected k wealthy cities to take the lead in setting up the freeway network. Here are the Silk Road Project’s rules: 1. In order to save costs, the freeway must be built at the basis on the original routes. 2. Every two selected cities can connect to each other by the freeway. 3. There will be no more than 10 unselected cities. Notice that there is NO city has the trade route connect to itself, and no more than ONE direct trade route between two cities.

输入格式
The input consists of T test cases. T is given in the first line of the input file.
Each test case begins with the first line containing three integer, n, m, k. n for n cities(2 <= n <= 100), m for m trade routes, k for k selected cities.
The second line for each case contains k positive integers representing the selected cities, numbered from 1 to n.
The following m lines contain triples of integers ai, bi, vi(1<=vi<=10000) . Where vi for the cost of building a freeway between ai and bi city.
There is an empty line after each test case.


输出格式
For each testcase, outputs should be set in one line.
If the Silk Road Project can be worked out, a positive integer should be printed to show the minimum cost.
Otherwise, the output should be “No solution!”.


输入样例
2

3 2 2
1 2
1 2 3
2 3 4

3 2 2
1 3
1 2 3
2 3 4


输出样例
3
7
搜索更多相关主题的帖子: selected network country setting cities 
2017-04-07 00:00
莫名Vet
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2017-3-6
收藏
得分:0 
这是我的代码


#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <deque>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
#define PB push_back
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define INF (1<<30)
#define eps (1e-8)
typedef     struct{
    int b;
    int cost;
}node;
vector < node > G[105];
int sele[105];
int vis[105];
int n,m,k;
long long ans;
int cnt;
void dfs(int i,int sum)
{
    vis[i]=1;
    if(k==0)
    {
        ans=min(ans,(long long)sum);
        return ;
    }
    int len=G[i].size();
    for(int j=0;j<len;j++)
    {
        if(!vis[G[i][j].b])
        {
            //printf("%d->%d\n",i,G[i][j].b);
            if(sele[G[i][j].b])    k--;
            dfs(G[i][j].b,sum+G[i][j].cost);
            if(sele[G[i][j].b]) k++;
            vis[G[i][j].b]=0;
        }   
    }
}
void solve()
{
    for(int i=0;i<105;i++)
        G[i].clear();
    scanf("%d%d%d",&n,&m,&k);
    int tmp;
    memset(sele,0,sizeof(sele));
    memset(vis,0,sizeof (vis));
    for(int i=0;i<k;i++)
    {   
        scanf("%d",&tmp);
        sele[tmp]=1;
    }
    int u,v,ca;
    node tmp1,tmp2;
    while(m--)
    {
        scanf("%d%d%d",&u,&v,&ca);
        tmp1.b=u,tmp1.cost=ca;   
        tmp2.b=v,tmp2.cost=ca;
        if(sele[u]||sele[v])
        {
            G[v].push_back(tmp1);
            G[u].push_back(tmp2);
        }
    }
    ans=INF;
    k--;
    dfs(tmp,0);
    if(ans==INF) printf("No solution!\n");
    else printf("%lld\n",ans);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
    return 0;   
}
2017-04-07 00:00
莫名Vet
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2017-3-6
收藏
得分:0 
只求教下怎么优化
2017-04-07 00:01
莫名Vet
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2017-3-6
收藏
得分:0 
时限是1200ms
2017-04-07 00:02
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:61 
虽然我还没有做到数据结构图这方面的内容~但有个优化思路~~
试试把dfs改为bfs~

具体点就是求bfs遍历点的部分最优解~
然后用这部分最优解一直推导到终点的最优解~

当所有点均被遍历或下一次广搜的所有节点代价均大于终点代价即可以停止搜索~

思路不难~弄弄结构框架应该可以实现~

[此贴子已经被作者于2017-4-7 02:11编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-07 02:10
快速回复:一道dfs的题,不会优化,求教怎么优化
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029085 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved