Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 31.10.2006, 17:05
Новичок

Отправить личное сообщение для master.wsd Посмотреть профиль Найти все сообщения от master.wsd
 
Регистрация: 31.10.2006
Сообщений: 8

задача 1379 тимус
Всем привет,
Помогите решить http://acm.timus.ru/problem.aspx?space=1&num=1379
Составил вроде простой алгоритм, ранее пользовался им для нахождения кратчайшего пути во взвешенном графе.
Получаю WA11. Что может быть неправильно? По идее, поиск как и для поиска кратчайшего пути во взвешенном графе, только с ограничениями на время и поток.

Код
#include <fstream>
#include <iostream>
#include <memory.h>

using namespace std;

int n, m;
bool proc[501];
int cups[501];
int time[501][501];
int weight[501][501];

int calc(int from, int cupslim, int timelim)
{
if (timelim < 0 || cupslim == 0)
return 0;

if (from == n - 1)
return cupslim;

if (proc[from])
return 0;

if (cups[from] < 0)
{
proc[from] = true;
int max = 0;
for (int i = 0;i < n;i++)
{
if (i == from) continue;
int cups = weight[from][i];
int t = time[from][i];
if (cups < 0) continue;
int loc = calc(i, cups, timelim - t);
if (loc > max) max = loc;
}

cups[from] = max;
proc[from] = false;
}
return cups[from];
}

int main()
{
#ifdef ONLINE_JUDGE
istream &in = cin;
#else
ifstream in("in.txt");
#endif

memset(proc, 0, sizeof(proc));
memset(cups, -1, sizeof(cups));
//memset(cupstime, 1441, sizeof(cupstime));

in >>n >>m;
for (int i = 0;i < m;i++)
{
int x, y;
in >>x >>y;
x--;y--;
in >>time[x][y] >>weight[x][y];
weight[x][y] -= 3000000;
weight[x][y] /= 100;
weight[y][x] =weight[x][y];
time[y][x] =time[x][y];
}

int res = calc(0, 10000000, 1440);
cout <<res;

#ifndef ONLINE_JUDGE
cin.get();
#endif

return 0;
}
  #2  
Старый 31.10.2006, 22:30
Пользователь

Отправить личное сообщение для AndreySUrSU Посмотреть профиль Найти все сообщения от AndreySUrSU
 
Регистрация: 06.10.2006
Адрес: Челябинск
Сообщений: 66

я не вдавался в твой код.
решение следующее:
перебираем массу дихотемией, ну и пытаемся провезти эту массу, если по ребру ее нельзя провезти, то этого ребра нет.
понятно, что с заданной массой можно уже и дейкстру запускать.
так и найдем макс массу, кот можно провезти за нужное время.
  #3  
Старый 01.11.2006, 15:49
Новичок

Отправить личное сообщение для Xepypr Посмотреть профиль Найти все сообщения от Xepypr
 
Регистрация: 01.11.2006
Адрес: Omsk
Сообщений: 10

В ней нужно использовать алгоритм Форда-Белмана.
он как раз по этой теме....
ps. Ты участвовал в Олимпиаде на тимусе 28.10 ?

Последний раз редактировалось Xepypr, 01.11.2006 в 16:51.
  #4  
Старый 01.11.2006, 16:37
Новичок

Отправить личное сообщение для master.wsd Посмотреть профиль Найти все сообщения от master.wsd
 
Регистрация: 31.10.2006
Сообщений: 8

Сообщение от Xepypr Посмотреть сообщение
В ней нужно использовать алгоритм Форда-Белмана.
он как раз по этой теме....
ps. Ты учавствовал в Олимпиаде на тимусе 28.10 ?
Как раз решил писать этим алгоритмом
WA25, уже веселее. Код прилагаю. Что не так?
Да, участвовал.

#include <fstream>
#include <iostream>
#include <memory.h>

using namespace std;

int n, m;
int cups[501];
int cupstime[501];
int time[501][501];
int weight[501][501];

int min(int m1, int m2)
{
if (m1 < m2)
return m1;
return m2;
}

int main()
{
#ifdef ONLINE_JUDGE
istream &in = cin;
#else
ifstream in("in.txt");
#endif

memset(cups, 0, sizeof(cups));
memset(weight, 0, sizeof(weight));
for (int i = 0;i < n;i++)
{
cupstime[i] = 1441;
for (int j = 0;j < n;j++)
time[i][j] = 1441;
}

in >>n >>m;
for (int i = 0;i < m;i++)
{
int x, y;
in >>x >>y;
x--;y--;
in >>time[x][y] >>weight[x][y];
weight[x][y] -= 3000000;
weight[x][y] /= 100;
weight[y][x] =weight[x][y];
time[y][x] = time[x][y];
}
cups[0] = 10000000;
cupstime[0] = 0;
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++)
{
if (i == j) continue;
int m = min(cups[j], weight[j][i]);
int t = cupstime[j] + time[j][i];
if (cups[i] < m && t < 1441)
{
cups[i] = m;
cupstime[i] = t;
}
}

cout <<cups[n-1];

#ifndef ONLINE_JUDGE
cin.get();
#endif

return 0;
}
  #5  
Старый 01.11.2006, 16:39
Новичок

Отправить личное сообщение для Xepypr Посмотреть профиль Найти все сообщения от Xepypr
 
Регистрация: 01.11.2006
Адрес: Omsk
Сообщений: 10

ну вроде как то))) какое место кстати?))))

Алгоритм Форда-Белмана, кажись он)
PHP код:
int a[100];

int Minst(int fromint toint n)            //from, to, min count 
{
    
int k,i,j,s;
    
int x[100],y[100];
    
    for(
i=1;i<=n;i++)
        
x[i] = a[from][i];

    while(
k!=n)
    {
        for(
s=1;s<=n;s++)
        {
            
y[s] = x[s];

            for(
i=1;i<=n;i++)
                if(
y[s]>x[i]+a[i][s])
                    
y[s] = x[i] + a[i][s];
            for(
i=1;i<=n;i++)
                
x[i] = y[i];
        }
        
k++;
    }
    return 
x[to];


Последний раз редактировалось Xepypr, 01.11.2006 в 17:00.
  #6  
Старый 02.11.2006, 16:32
Новичок

Отправить личное сообщение для master.wsd Посмотреть профиль Найти все сообщения от master.wsd
 
Регистрация: 31.10.2006
Сообщений: 8

ну так я его и написал.
мне кажется, у меня проблема в определении времени...

место не помню, 3 задачи за час
  #7  
Старый 02.11.2006, 18:20
Пользователь

Отправить личное сообщение для AndreySUrSU Посмотреть профиль Найти все сообщения от AndreySUrSU
 
Регистрация: 06.10.2006
Адрес: Челябинск
Сообщений: 66

по-моему тут более логична дихотемия с дейкстрой. да и быстрее она работает. и проблем там не должно возникать.
хотя если беллман - правильное решение, то и тут не должно возникнуть.
  #8  
Старый 02.11.2006, 18:41
Новичок

Отправить личное сообщение для Anton [SUrSU] Посмотреть профиль Найти все сообщения от Anton [SUrSU]
 
Регистрация: 02.11.2006
Сообщений: 16

решение - бинарный поиск по ответу + дейкстра! работает оч. быстро
  #9  
Старый 02.11.2006, 19:13
Новичок

Отправить личное сообщение для master.wsd Посмотреть профиль Найти все сообщения от master.wsd
 
Регистрация: 31.10.2006
Сообщений: 8

Сообщение от Anton [SUrSU] Посмотреть сообщение
решение - бинарный поиск по ответу + дейкстра! работает оч. быстро
Я это уже просек. При сложности O(N*N)*logN и N=500 очевидно проблем со временеи не будет.
Просто хочу другим способом решить
Как думаете, возможно?
  #10  
Старый 03.11.2006, 02:22
Новичок

Отправить личное сообщение для Anton [SUrSU] Посмотреть профиль Найти все сообщения от Anton [SUrSU]
 
Регистрация: 02.11.2006
Сообщений: 16

А при чем тут Беллман-Форд, я не вкурил?!
У него сложность, как мне помнится O(n^3), многовато будет для n=500, вам не кажется?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра