洛谷P134② 请柬

九. 着力台站建设

★★☆   输入文件:zpj.in   输出文件:zpj.out   容易相比
日子范围:1 s   内部存款和储蓄器限制:12八 MB

【难题讲述】

    n个城市之间有报导网络,从那n个市场中选定几座城市和市镇,在那里建立基本台站,要求它们与别的各城市和市镇周边,同时为减低造价,要使中央台站多少最少。

【输入格式】

输入文件有好多行
首先行,二个平头n,表示共有n个城市(2<=n<=100)
上面有n行,每行有n个数字。第p行第q列的数字代表城市和市镇p与乡镇q之间有无直接通信线路。数字为一意味有,0表示无。

【输出格式】

出口文件有若干行
第叁行,二个整数a,表示最少中央台站数据。

第一行二个整数b,表示共有b种方案。上边有b行,每行有a个整数,表示一种建站方案。二种方案输出时,输出顺序按城市和市集编号由小到大字典序输出。

【输入输出样例】

输入文件名: zpj.in

6

0 1 1 1 0 0

1 0 0 1 0 0

1 0 0 0 1 0

1 1 0 0 0 1

0 0 1 0 0 1

0 0 0 1 1 0

输出文件名:zpj.out

2

5

1 5

1 6

2 5

3 4

4 5

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 101
#define mod 1000003
using namespace std;
int n,mn=1000,ans;
char buf[20000],tmp[2000];
bool e[maxn][maxn],pkd[maxn],ht[mod];
bool try_Insert(){
    int hv=0,fac=1;
    for(int i=1;i<=n;i++){
        if(pkd[i]){
            hv+=fac;
            hv%=mod;
        }
        fac*=2;
        fac%=mod;
    }
    if(ht[hv])return 0;
    else return ht[hv]=1;
}
void dfs(int u,int now){
    if(now>mn)return;
    if(u>n){
        if(now<mn)mn=now,ans=0,buf[0]=0;
        if(!try_Insert())return;
        tmp[0]=0;
        ans++;
        for(int i=1;i<=n;i++)
            if(pkd[i])sprintf(tmp+strlen(tmp),"%d ",i);
        sprintf(tmp+strlen(tmp),"\n");
        strcat(buf,tmp);
    }
    else{
        bool flag=0;
        for(int v=1;v<=n;v++)
            if(e[u][v])
                if(pkd[v]){
                    if(!flag)flag=1,dfs(u+1,now);
                }
                else{
                    pkd[v]=1;
                    dfs(u+1,now+1);
                    pkd[v]=0;
                }
    }
}
int main(){
    freopen("zpj.in","r",stdin);freopen("zpj.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&e[i][j]);
            if(i==j)e[i][j]=1;
        }
    dfs(1,0);
    cout<<mn<<endl<<ans<<endl<<buf;
}

 

P1342 请柬

难点叙述

在电视机时期,未有稍微人收看戏剧表演。Malidinesia古董喜剧歌手意识到那壹真情,他们想宣传剧院,尤其是古色古香的现代片。他们曾经打字与印刷请帖和具备须要的新闻和安顿。许多学生被雇来散发那一个请柬。每个学生志愿者被钦点2个适中的共用小车站,他或他将留在这里①整天,诚邀人们加入。

此地的公共交通系统是那几个越发的:全体的路线都以单向的,连接八个站点。公共小车相距开头点,到达指标地之后又空车再次回到早先点。学生每一天早上从总部出发,乘公共交通车到三个预定的站点约请旅客。每一种站点都被安插了一名学员。在一天停止的时候,全数的学生都回到总部。今后内需知道的是,学生所需的公共交通开支的总额最小是多少。

输入输出格式

输入格式:

 

第2行有五个整数n、m(一<=n,m<=1000000),n是站点的个数,m是线路的个数。

接下来有m行,每行描述3个线路,包含二个整数,起首点,目的地和价格。

总部在第1个站点,价钱都是整数,且小于一千000000。

 

出口格式:

 

出口一行,表示小小的费用。

 

输入输出样例

输入样例#1: 复制

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

出口样例#1: 复制

210 

说明

【注意】

此题数据规模较大,须要接Nabi较高效的算法,此题不设小范围数据分数。

/*
    正向建一个图,反向建一个图,跑两遍最短路即可,我用的SLF优化spfa
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 1000010
using namespace std;
int n,m,num,head[maxn],num2,head2[maxn];
long long ans=0,dis[maxn];
bool vis[maxn];
struct node{
    int to,pre,v;
}e[maxn],e2[maxn];
void Insert(int from,int to,int v){
    e[++num].to=to;
    e[num].v=v;
    e[num].pre=head[from];
    head[from]=num;
}
void Insert2(int from,int to,int v){
    e2[++num2].to=to;
    e2[num2].v=v;
    e2[num2].pre=head2[from];
    head2[from]=num2;
}
void spfa1(){
    deque<int>q;q.push_back(1);
    for(int i=1;i<=n;i++)dis[i]=1234567890;
    memset(vis,0,sizeof(vis));
    vis[1]=1;dis[1]=0;
    while(!q.empty()){
        int now=q.front();q.pop_front();vis[now]=0;
        for(int i=head[now];i;i=e[i].pre){
            int to=e[i].to;
            if(dis[to]>dis[now]+e[i].v){
                dis[to]=dis[now]+e[i].v;
                if(!vis[to]){
                    vis[to]=1;
                    if(!q.empty()&&dis[to]<dis[q.front()])q.push_front(to);
                    else q.push_back(to);
                }
            }
        }
    }
    for(int i=2;i<=n;i++)ans+=dis[i];
}
void spfa2(){
    deque<int>q;q.push_back(1);
    for(int i=1;i<=n;i++)dis[i]=1234567890;
    memset(vis,0,sizeof(vis));
    vis[1]=1;dis[1]=0;
    while(!q.empty()){
        int now=q.front();q.pop_front();vis[now]=0;
        for(int i=head2[now];i;i=e2[i].pre){
            int to=e2[i].to;
            if(dis[to]>dis[now]+e2[i].v){
                dis[to]=dis[now]+e2[i].v;
                if(!vis[to]){
                    vis[to]=1;
                    if(!q.empty()&&dis[to]<dis[q.front()])q.push_front(to);
                    else q.push_back(to);
                }
            }
        }
    }
    for(int i=2;i<=n;i++)ans+=dis[i];
}
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        Insert(x,y,z);Insert2(y,x,z);
    }
    spfa1();
    spfa2();
    cout<<ans;
}