题解 - Vijos

13

PowderHan LV 10 @ 2017-05-07 22:19:57

/*
嗯典型的最小环问题
因为n很小可以直接Floyd求最小环
注意最小环ans更新的位置
每次枚举k为下家更新点
应该先尝试更新ans再更新i,j之间的最短路
我们用g[i][j]来记录i,j之间最短路径
而w[i][j]用来保存i,j之间的原始路径长度
因为我们知道i,j要构成一个最小环
肯定要有两条路可走
1.直接从i到j。
2.从i经过某个中途点k到达j
即对于每一个k 我们先尝试从这个k点对于所有的i,j点能不能得到最小环
然后我们再用这个k点尝试更新路径
该算法的证明:
一个环中的最大结点为K（编号最大），与其相连的两个点为i,j ，
这个环的最短长度为： g[i][k] + g[k][j] + i到j的路径中所有结点编号都不大于k的最短路径长度，
根据floyd的原理，在最外层循环做一个k-1次之后，
g[i][j] 则代表了i到j的路径中所有结点的编号都不大于k的最短路径。
所以我们枚举的i,j要有
1<=i<k,i<j<k
再换一种说法吧
比普通Floyd多出来的部分,主要利用到的原理是当处理到k时,
所有以1 到k - 1为中间结点的最短路径都已经确定，
则这时候的环为（i到j(1 < i, j <= k - 1)的最短路径） + 边（i, k） + 边（k, j）
遍历所有的i, j找到上述式子的最小值即位k下的最小代价环  
这样总能懂了吧QAQ
*/
/*
路径的求法：
用一个pre[i][j]记录j前面的一个顶点， 初始化为i，当出现需要更新的时候则将pre[i][j] = pre[k][j];
若i== j的时候则表示找全了路径，最后将k点加入路径中 
核心代码：
While(i ！= j)
{  
    if (i != j) 
    {  
        Path[len++] = j;
        J = pre[i][j]; 
    }  
     Path[len++] = i;
}
http://wenku.baidu.com/view/c6382a41a8956bec0975e3c0.html?from=related
http://blog.csdn.net/youngyangyang04/article/details/7054931
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int INF=1e8;
int w[102][102],g[102][102];
int n,e;

void init()
{
    int x,y,v;
    for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                w[i][j]=g[i][j]=INF;
    for(int i=1;i<=e;i++)
    {
        scanf("%d%d%d",&x,&y,&v);
        w[x][y]=w[y][x]=g[x][y]=g[y][x]=v;
    }
}

void work()
{
    int ans=INF;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)//最小环
            for(int j=i+1;j<k;j++)//为了避免一条边计算两次并且i == j时因为权重会出错 
                ans=min(ans,g[i][j]+w[i][k]+w[k][j]);
        for(int i=1;i<=n;i++)//Floyd
            for(int j=1;j<=n;j++)
                if(i!=j)
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    }
    if(ans==INF)
        cout<<"No solution."<<endl;
    else
        cout<<ans<<endl;
}

int main()
{
    while(scanf("%d%d",&n,&e)!=EOF)
    {
        init();
        work();
    }
}

4

清风breeze LV 8 @ 2017-11-23 13:42:05

#include<cstdio>
#define maxn 5010
#define INF 1<<24
int dist[maxn][maxn], g[maxn][maxn];
int n, m;
void init() {
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
dist[i][j]=g[i][j]=INF;
int u, v, w;
for(int i=0; i<m; ++i) {
scanf("%d%d%d", &u, &v, &w);
if(dist[u][v]>w) {
dist[u][v]=dist[v][u]=w;
g[u][v]=g[v][u]=w;
}
}
}
void solve() {
int _min=INF, cnt=0;
for(int k=1; k<=n; ++k) {
for(int i=1; i<k; ++i)
if(g[i][k]^INF)
for(int j=i+1; j<k; ++j) {
int tmp=dist[i][j]+g[i][k]+g[k][j];
if(tmp<_min) {
_min=tmp;
cnt=1;
} else if(tmp==_min) cnt++;
}
for(int i=1; i<=n; ++i)
if(dist[i][k]^INF)
for(int j=1; j<=n; ++j)
if(dist[k][j]^INF) {
int tmp=dist[i][k]+dist[k][j];
if(tmp<dist[i][j]) dist[i][j]=tmp;
}
}
if(cnt>0) printf("%d\n", _min);
else printf("No solution.\n");
}
int main() {
while(scanf("%d%d",&n,&m)!=EOF) {
init();
solve();
}
return 0;
}

3

lecision LV 7 @ 2015-03-11 13:03:47

最小环问题
<1>朴素的算法：
令e(u,v)表示u和v之间的连边，再令min(u,v)表示，删除u和v之间的连边之后，u和v之间的最短路
最小环则是min(u,v) + e(u,v)，时间复杂度是EV2。
<2>改进的方法：
在floyd的同时，顺便算出最小环
g[i][j]=(i,j之间的边长)
dist:=g;
for k:=1 to n do
begin
for i:=1 to k-1 do
for j:=i+1 to k-1 do
answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
for i:=1 to n do
for j:=1 to n do
dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
end;
关于算法<2>的证明：
一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度
根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径
综上所述，该算法一定能找到图中最小环。
#include<stdio.h>
const long max=1000000;
long n,m,x,y,d;
long dist[111][111],map[111][111],ans;
long min(long a,long b)
{
if(a<b) return a;
else return b;
}
int main()
{
int i,j,k;
while(scanf("%ld%ld",&n,&m)!=EOF)
{
// ;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) map[i][j]=max;
for(i=1;i<=m;i++)
{
scanf("%ld%ld%ld",&x,&y,&d);
map[x][y]=d;
map[y][x]=d;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) dist[i][j]=map[i][j];
ans=max;
for(k=1;k<=n;k++)
{
for(i=1;i<=k-1;i++)
for(j=i+1;j<=k-1;j++)
ans=min(dist[i][j]+map[i][k]+map[k][j],ans);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
if(ans==max) printf("No solution.\n");
else printf("%ld\n",ans);
}
return 0;
}

1

Dream丶Mingfeng LV 5 @ 2017-11-23 13:40:28

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 108
#define INF 1<<24
int dist[maxn][maxn], g[maxn][maxn];
int n, m;
void init(){
for ( int i=1; i<=n; ++i )
for ( int j=1; j<=n; ++j )
dist[i][j] = g[i][j] = INF;
int u, v, w;
for ( int i=0; i<m; ++i ) {
scanf("%d%d%d", &u, &v, &w);
if(dist[u][v] > w) {
dist[u][v] = dist[v][u] = w;
g[u][v] = g[v][u] = w;
}
}
};

void solve(){
int minn = INF, cnt=0;
for ( int k=1; k<=n; ++k ){
for ( int i=1; i<k; ++i ) if(g[i][k]^INF)
for( int j=i+1; j<k; ++j ) if(dist[i][j]^INF && g[k][j]^INF)
{
int tmp = dist[i][j]+g[i][k]+g[k][j];
if(tmp < minn ) {
minn = tmp; cnt=1;
}else if(tmp == minn) ++cnt;
}
for(int i=1; i<=n; ++i ) if(dist[i][k]^INF)
for(int j=1; j<=n; ++j ) if(dist[k][j]^INF)
{
int tmp= dist[i][k]+dist[k][j];
if(tmp < dist[i][j]) dist[i][j] = tmp;
}
}
if(cnt > 0) printf("%d\n", minn);
else printf("No solution.\n");
}

int main(){
while(scanf("%d%d", &n, &m)!=EOF){

init();
solve();
}
return 0;

}

0

zyc2000 LV 9 @ 2018-02-15 08:01:30

状态  题目  递交者     时间  内存  语言  递交时间
Accepted
    P1046 观光旅游  zyc2000     225ms   508.0 KiB   C++     48秒前
Wrong Answer
    P1046 观光旅游  zyc2000     223ms   512.0 KiB   C++     2分钟前
Wrong Answer
    P1046 观光旅游  zyc2000     183ms   488.0 KiB   C++     5分钟前
Wrong Answer
    P1046 观光旅游  zyc2000     267ms   504.0 KiB   C++     8分钟前
Wrong Answer
    P1046 观光旅游  zyc2000     162ms   512.0 KiB   C++     10分钟前
Wrong Answer
    P1046 观光旅游  zyc2000     215ms   512.0 KiB   C++     13分钟前
Wrong Answer
    P1046 观光旅游  zyc2000     289ms   488.0 KiB   C++     16分钟前
Wrong Answer
    P1046 观光旅游  zyc2000     326ms   480.0 KiB   C++     18分钟前
Wrong Answer
    P1046 观光旅游  zyc2000     281ms   616.0 KiB   C++     1天前
Time Exceeded
    P1046 观光旅游  zyc2000     ≥6043ms     ≥384.0 KiB  C++     2周前

统统WA，原因竟是

No solution. S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！S是小写！

#include<cstdio>
#include<iostream>
#define MAXN 105
#define INF 100000000
using namespace std;

int n, m;
int o[MAXN][MAXN];
int f[MAXN][MAXN];

int main(){
  int tfrom, tto, tw;
  while(cin >> n >> m){
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
        o[i][j] = f[i][j] = INF;
      }
    }
    for(int i=0; i<m; i++){
      cin >> tfrom >> tto >> tw;
      o[tfrom][tto] = o[tto][tfrom] = f[tfrom][tto] = f[tto][tfrom] = min(o[tfrom][tto], tw);
    }
    int gans = INF;
    for(int k=1; k<=n; k++){
      for(int i=1; i<k; i++){
        for(int j=i+1; j<k; j++){
          // if(f[i][j] < INF && o[i][k] < INF && o[k][j] < INF){
            gans = min(gans, f[i][j]+o[i][k]+o[k][j]);
          // }
        }
      }
      for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
          if(i == j) continue;
          f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
        }
      }
    }
    if(gans < INF){
      cout << gans << endl;
    }else{
      cout << "No solution." << endl;
    }
  }

  return 0;
}

0

Dream丶Mingfeng LV 5 @ 2017-11-23 13:40:20

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 108
#define INF 1<<24
int dist[maxn][maxn], g[maxn][maxn];
int n, m;
void init(){
for ( int i=1; i<=n; ++i )
for ( int j=1; j<=n; ++j )
dist[i][j] = g[i][j] = INF;
int u, v, w;
for ( int i=0; i<m; ++i ) {
scanf("%d%d%d", &u, &v, &w);
if(dist[u][v] > w) {
dist[u][v] = dist[v][u] = w;
g[u][v] = g[v][u] = w;
}
}
};

void solve(){
int minn = INF, cnt=0;
for ( int k=1; k<=n; ++k ){
for ( int i=1; i<k; ++i ) if(g[i][k]^INF)
for( int j=i+1; j<k; ++j ) if(dist[i][j]^INF && g[k][j]^INF)
{
int tmp = dist[i][j]+g[i][k]+g[k][j];
if(tmp < minn ) {
minn = tmp; cnt=1;
}else if(tmp == minn) ++cnt;
}
for(int i=1; i<=n; ++i ) if(dist[i][k]^INF)
for(int j=1; j<=n; ++j ) if(dist[k][j]^INF)
{
int tmp= dist[i][k]+dist[k][j];
if(tmp < dist[i][j]) dist[i][j] = tmp;
}
}
if(cnt > 0) printf("%d\n", minn);
else printf("No solution.\n");
}

int main(){
while(scanf("%d%d", &n, &m)!=EOF){

init();
solve();
}
return 0;

}

0

午后奶茶 LV 8 @ 2009-11-07 11:50:10

chrome果然不能提交

两次No Complied

我的通过率啊

0

syh173 LV 9 @ 2009-11-06 18:50:56

这题真怪，我开始

1.fillchar(a,sizeof(a),1); 90分

2.for i:=1 to n do

for j:=1 to n do

a:=100000000;

Ac..

百思不得其解。。

好人族 @ 2013-02-15 15:09:54

fillchar1的话会出错，我以前就是栽在了那上面（实际上是昨天呵呵）。
KevinWang @ 2013-10-31 16:38:36

maxlongint过程中会加爆的

0

527971925 LV 10 @ 2009-11-06 00:08:45

最小环，就是最小环，不会做！

那么我就把它背下来呗！

结果写的时候写错了....

for k:=1 to n do

for i:=1 to k-1 do

for j:=i+1 to k-1 do

写成了：

for k:=1 to n do

for i:=1 to k-1 do

for j:=1 to k-1 do

。。。。。

---|---|---|---|---|---|---|---|---|

const maxnum=16843009;

var

n,m,r:longint;

map,f:array[0..100,0..100]of longint;

procedure main;

var

i,a,k,j,b,c:longint;

begin

readln(n,m);

fillchar(map,sizeof(map),1);

for i:=1 to m do

begin

readln(a,b,c);

map[a,b]:=c;

map:=c;

end;

for i:=1 to n do map:=0;

f:=map;

r:=maxnum;

for k:=1 to n do

begin

for i:=1 to k-1 do

for j:=i+1 to k-1 do

if f+map[j,k]+map[k,i]f+f[k,j] then

f:=f+f[k,j];

end;

if r

0

sixhomeland LV 9 @ 2009-11-03 11:04:05

交了11次终于过了！！！

居然不能用IE交题？！

No solution自动进化成了no solution！

……

0

wangjunyong LV 7 @ 2009-10-30 10:05:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

floyd最小环

0

淘淘 LV 8 @ 2009-10-25 20:52:57

多谢huyuanming11提醒...

0

brace_123 LV 9 @ 2009-10-20 22:39:59

Floyd求最小环问题

Accepted 有效得分：100 有效耗时：725ms

Sunny和我有仇么？。。今天3个Floyd的程序都这么丑的时间

0

SecretAgent LV 10 @ 2009-10-18 10:31:53

对输入格式描述中的第一句话

和注释中的第一句话比较无语.

做法楼下的牛们已经说得很清楚了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 72ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：303ms

0

huyuanming11 LV 10 @ 2009-10-04 18:27:53

终于AC了......

注意inf = 1000000000 会爆

原因（我猜想的）：

在普通Floyed中

g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

inf = 1e9没有任何问题，因为int上限大于2e9

而在Floyed改进算法中，

ans = min(ans, d[i][k] + d[k][j] + g[i][j]);

如果3个加数都是inf, 和就是3e9,int就爆了......

所以，保险起见，inf = 1e8

0

芒果木瓜榴莲 LV 9 @ 2009-09-23 18:27:13

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

交了N遍才过。。。原来读入的时候要用readln……终于明白了……

但是

这是一种怎样的floyed改进？

0

beakham LV 8 @ 2009-09-18 13:13:36

莫名其妙 max：=1000000000 就80

设成100000000 就AC 数据有问题

0

mintalfance LV 10 @ 2009-09-16 20:19:45

program p1046;

var a,f:array[1..100,1..100] of longint;

i,j,k,l,m,n,p,q,r,max:longint;

begin

while not eof do begin

fillchar(a,sizeof(a),0);

readln(n,m);

for i:=1 to n do

for j:=1 to n do a:=10000000;

for i:=1 to m do

begin readln(p,q,r);a[p,q]:=r;a[q,p]:=r; end;

for i:=1 to n do a:=0;f:=a;max:=10000000;

for k:=1 to n do begin

for i:=1 to k-1 do

for j:=i+1 to k-1 do

if f+a+a[k,j]

0

kimizhang LV 10 @ 2009-09-16 15:37:30

Floyed求最小环,发个程序,下面的讲的太抽象.

Const Maxn=100;

INF=1000000;

Var matrix,f:array[1..Maxn,1..Maxn]of longint;

n,m:longint;

Procedure readp;

var i,u,v,t:longint;

begin

readln(n,m);

filldword(matrix,sizeof(matrix)div 4,INF);

for i:=1 to m do begin

readln(u,v,t);

matrix:=t;

matrix[v,u]:=t;

end;

for i:=1 to n do

matrix:=0;

f:=matrix;

end;

Procedure solve;

var i,j,k,ans:longint;

begin

ans:=INF;

for k:=1 to n do begin

for i:=1 to k-1 do

for j:=i+1 to k-1 do

if f+matrix+matrix[k,j]

0

zhh1993 LV 10 @ 2009-09-10 17:02:24

神奇的方法~又长见识了~~

其实filldword真的很方便....

题解

120 条题解

观光旅游

信息

状态

开发

支持

题解

120 条题解

观光旅游

信息

状态

开发

支持

还没有账户？

登录