95992828九五至尊2

月孛星移民,最小生成树

二月 12th, 2019  |  617888九五至尊2

2283: [Sdoi2011]紫炁星移民

Time Limit: 40 Sec  Memory Limit: 512 MB
Submit: 119  Solved: 56
[Submit][Status][Discuss]

Time Limit: 10 Sec  Memory
Limit: 162 MB
Submit: 4021  Solved: 2257
[Submit][Status][Discuss]

Description

Description

给您一个无向图,N(N<=500)个极端,
M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你三个顶峰S和T,求

一条路子,使得路径上最大边和微小边的比率最小。如果S和T之间从未门路,输出”IMPOSSIBLE”,否则输出这么些

比值,若是急需,表示成一个既约分数。 备注: 两个极端之间恐怕有多条路子。

在2xyz年,人类曾经移民到了土星上。由于工业的要求,人们开首在金星上采矿。紫炁星的矿区是一个边长为N的正六边形,为了便于统筹,整个矿区被分成6*N*N个正三角形的区域(如图1)。

 617888九五至尊2 1

 

漫天矿区中存在A矿,B矿,C矿两个矿场,和a厂,b厂,c厂多个炼矿厂。各个三角形的区域可以是一个矿场、炼矿厂、山地、可能平地。将来矿区管理局需要树立一个交通系统,使得矿场和对应炼矿厂之间存在一条公路,并且三条公路互不交叉(即一个三角区域中不设有两条以上运输差异矿的公路)。多少个三角形区域是隔壁的当且仅当那多少个三角存在公共边,唯有附近的几个区域之间才能建一段路,建那段路的支出为1。注意,山地上是不可以建公路的。由于木星金融危害的影响,矿区管理局想知道建立那样一个交通系统最少要花多少开支。更加多的,当局向知情有些许种消费最小的方案。

Input

先是行包涵八个正整数,N和M。下来的M行每行包涵八个正整数:x,y和v。表示景点x到景点y之间有一条双向公路

,车辆必须以速度v在该公路上行驶。最终一行包涵四个正整数s,t,表示想驾驭从景点s到景点t最大不大速度比

小小的的不二法门。s和t不容许同样。

1<N<=500,1<=x,y<=N,0<v<30000,0<M<=5000

Input

第1行一个整数N。表示那几个矿区是边长为N的正六边形。

接下去有6*N*N的整数,分为2*N行,表示矿区脚下区域的图景。0意味平地,1,2,3表示对应的矿区要么炼矿厂,4象征山地。(样例1对应图2)。可能有多组数据,请处理到文件结尾

 

Output

比方景点s到景点t没有门路,输出“IMPOSSIBLE”。否则输出一个数,表示小小的的速度比。

若果须求,输出一个既约分数。

Output

对此每组数据,包括三个整数,表示很小花费和落得最小开支的方案数。假设找不到符合须求的方案,输出-1
-1。由于方案数只怕过大,所以请把方案数mod 1000000007

 

 

Sample Input

【样例输入1】
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
617888九五至尊2,1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3

Sample Input

【样例输入1】
2
0 1 0 0 0
0 0 2 0 4 0 0
0 0 4 3 0 3 2
0 0 0 1 0

【样例输入2】
3
0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0 0
0 3 0 1 0 2 0

Sample Output

【样例输出1】
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2

Sample Output

【样例输出1】
18 1
【样例输出2】
44 1

HINT

HINT

 

样例2的解释

617888九五至尊2 2

 

 

对于100%的数据,N≤6

 

Source

设想到$N, M$很小,所以考虑$(N/M)^2$级其他算法

刚开端我很zz的觉得答案在细微/最大生成树上,

然而

1 2 2

2 3 4

1 3 5

那组数据就足以卡掉。

设想什么化解那种难点。

大家得以枚举最小值所在的边,然后把比她权值大的边往上加。假设S和T联通了就淡出

这么自然是对的。

日子复杂度$O(M^2)$

#include<cstdio>
#include<algorithm>
#define LL long long  
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
using namespace std;
inline int read() {
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
struct Edge {
    int u, v, w;
    bool operator < (const Edge &rhs) const {
        return w < rhs.w;
    }
}E[MAXN];
int N, M, fa[MAXN], S, T;
int find(int x) {
    if(fa[x] == x) return fa[x];
    else return fa[x] = find(fa[x]);
}
int Build(int now) {
    int mx = -INF, tot = 0;
    for(int i = 1; i <= N; i++) fa[i] = i;
    for(int i = now; i <= M; i++) {
        int fx = find(E[i].u), fy = find(E[i].v);
        if(fx == fy) continue;
        tot++;
        fa[fx] = fy;
        mx = max(mx, E[i].w);
        if(find(S) == find(T)) return mx;
    }
    return INF;
}
main() {
    N = read(); M = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        E[i] = (Edge){x, y, z};
    }
    S = read(), T = read();
    sort(E + 1, E + M + 1);
    double now = INF;
    int mi = INF, mx = INF;
    for(int i = 1; i <= M; i++) {
        int nowx = Build(i);
        if((double)nowx / E[i].w < now) {
            mi = E[i].w, mx = nowx;
            now = (double)mx / mi;
        }
    }
    if(mx == INF) printf("IMPOSSIBLE");
    else {
        int gcd = __gcd(mi, mx);
        if(mi / gcd != 1) printf("%d/%d", mx / gcd, mi / gcd);
        else printf("%d", mx / gcd);
    }
}

 

Source

stage 2
day1

//40分dfs
//插头dp不会
#include<cstdio>
#include<cstring>
using namespace std;
const int N=70;
const int dx[2][3]={{1,0,0},{-1,0,0}};
const int dy[2][3]={{0,1,-1},{0,1,-1}};
int n,sx[4],sy[4],ex[4],ey[4],mp[N][N];bool vis[N][N];
int ans,sum;
inline void Cl(){
    memset(mp,-1,sizeof mp);
    memset(vis,0,sizeof vis);
    memset(sx,0,sizeof sx);
    memset(sy,0,sizeof sy);
    memset(ex,0,sizeof ex);
    memset(ey,0,sizeof ey);
}
inline void init(){
    for(int i=1;i<=n;i++){
        for(int j=n-i+1;j<=n*3+i-1;j++){
            scanf("%d",&mp[i][j]);
            int &db=mp[i][j];
            if(db>0&&db<4){
                if(!sx[db]) sx[db]=i,sy[db]=j;
                else ex[db]=i,ey[db]=j;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n*4-i;j++){
            scanf("%d",&mp[i+n][j]);
            int &db=mp[i+n][j];
            if(db>0&&db<4){
                if(!sx[db]) sx[db]=i+n,sy[db]=j;
                else ex[db]=i+n,ey[db]=j;
            }
        }
    }
}
void dfs(int now,int x,int y,int cost){
    if(x==ex[now]&&y==ey[now]){
        if(now<3){
            vis[sx[now+1]][sy[now+1]]=1;
            dfs(now+1,sx[now+1],sy[now+1],cost);
            vis[sx[now+1]][sy[now+1]]=0;
        } 
        else{
            if(cost==ans) sum++;
            if(cost<ans) ans=cost,sum=1;
        }
        return ;
    }
    int p=!((x+y&1)^(n&1));
    for(int i=0,nx,ny;i<3;i++){
        nx=x+dx[p][i];ny=y+dy[p][i];
        if(!vis[nx][ny]&&(!mp[nx][ny]||mp[nx][ny]==now)){
            vis[nx][ny]=1;
            dfs(now,nx,ny,cost+1);
            vis[nx][ny]=0;
        }
    }
}
inline void work(){
    Cl();init();
    ans=2e9;sum=0;
    vis[sx[1]][sy[1]]=1;
    dfs(1,sx[1],sy[1],0);
    if(sum) printf("%d %d\n",ans,sum);
    else printf("-1 -1\n");
}
int main(){
    freopen("mars.in","r",stdin);
    freopen("mars.ans","w",stdout);
    while(~scanf("%d",&n)) work();
    return 0;
} 

 

相关文章

Your Comments

近期评论

    功能


    网站地图xml地图