Может ли кто-нибудь помочь мне с этим проблема Я пытаюсь это в течение нескольких дней. Я получаю неправильный ответ каждый раз. Я использовал метод Эдмондса — Карпа … Вот мой код:
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#define MAXX 900000000
using namespace std;
long int capacity[5005][5005] ;
int graph[5005][5005] , v[5005] , from[5005] ;
//Calculating Max Flow using Edmond karp
int Max_Flow(int s , int t)
{ queue<int>Q ;
// Bfs to get the paths from source to sink
Q.push(s) ;
v[s] = 1 ;
int r ;
long long int min ;
while(!Q.empty())
{ int p = Q.front() ;
Q.pop();
r = 0 ;
for(int j = 0 ; graph[p][j]!=0 ; j++)
{
if(!v[graph[p][j]]&&capacity[p][graph[p][j]])
{ Q.push(graph[p][j]) ; from[graph[p][j]] = p ;
v[graph[p][j]] = 1 ;
if(graph[p][j]==t)
{ r = 1 ; break ; }
}
}
if(r==1)
break ;
}
r = t ;
min = MAXX ;
// Caculating the minimum capacity over the path found by BFS
while(from[r]!=0)
{
if(min>capacity[from[r]][r])
min = capacity[from[r]][r] ;
r = from[r] ;
}
r = t ;
//Subtracting the min capacity found over the path
while(from[r]!=0)
{
capacity[from[r]][r]-=min;
capacity[r][from[r]]+=min;
r = from[r] ;
}
if(min==MAXX)
return 0;
else
return min;
}
int main()
{
int t , n , s , c , i , j , k , a , b , p = 0 ;
unsigned long long int flow , r ;
memset(capacity,0,sizeof(capacity));
memset(from,0,sizeof(from));
memset(graph,0,sizeof(graph));
memset(v,0,sizeof(v));
scanf("%d%d",&n,&c);
for(i = 0 ; i<c ; i++)
{
scanf("%d%d%d",&a,&b,&k);
if(b!=a)
{
capacity[a][b]+=k ;
capacity[b][a]+=k ;
j = 0 ;
r = 0 ;
while(graph[a][j]!=0)
{ if(graph[a][j]==b)
{ r = 1 ; break ; }
j++;
}
if(!r) graph[a][j] = b ;
j = 0 ;
r = 0 ;
while(graph[b][j]!=0)
{ if(graph[b][j]==a)
{ r = 1 ; break ; }
j++;
}
if(!r) graph[b][j] = a ;
}
}
flow = 0 ;
r = 1 ;
while(r)
{ flow+=r ;
r = Max_Flow(1,n) ;
memset(from,0,sizeof(from));
memset(v,0,sizeof(v));
}
printf("%lld\n",flow-1);return 0;
}
Как сказано в постановке задачи: «Обратите внимание, что возможно наличие дублирующих ребер, а также ребра от узла к себе». Поэтому я проигнорировал циклы self и добавил емкость повторяющихся ребер в массиве «Capacity», соответствующий этим узлам. Я создал «график» и выполнял BFS от источника до приемника, чтобы получить пути, пока все пути не будут увеличены. Я суммировал все найденные минимальные значения и напечатал ответ … Кто-нибудь может объяснить, почему неправильный ответ?
Предположим, у вас был простой график с одним ребром между началом и концом с емкостью 1 миллиард.
Как ваш MAXX < 1 миллиард, когда вы запустите Max_Flow, вы обнаружите поток MAXX и ошибочно заключите, что это означало, что не было найдено пути расширения.
Если это так, попробуйте заменить
#define MAXX 900000000
с
#define MAXX 1100000000
и программа может пройти …
Других решений пока нет …