Hello everyone. I have just encountered with this problem and I have solved it with Edmonds- Karp's maximal flow algorithm.
But got TLE(Time Limit Exceeded) verdict. What algorithm must I use to avoid TLE? Please give me an idea. Thank you in advance.
1 2015-02-22 12:05:10
Re: Problem (3 ответов, оставленных в Problems)
3 2013-04-13 22:10:42
Тема: Игра (6 ответов, оставленных в Problems)
Пожалуйста помогите решить эту задачу
N мальчиков стоят по кругу. Они начинают считать себя по часовой стрелке, счет ведется с единицы. Как только количество посчитанных достигает p, последний посчитанный (p-й) мальчик покидает круг, а процесс счета начинается со следующего за ним мальчика и вновь ведется с единицы. Последний оставшийся в кругу выигрывает. Мальчики нумеруются числами от 1 до N по часовой стрелке, начиная с того самого мальчика, с которого начинался счет. 1<=N,P<=10^6.
Надо найти номер выигрывшего мальчика в исходном кругу.
4 2013-02-15 19:45:33
Тема: SEQUENCE PERMUTATION (1 ответов, оставленных в Problems)
I have not any algorithm for this problem. Can I solve this problem with DP?
Any algorithm please.
You are given a sequence 1, 2, .., N. M times, you pick two adjacently located numbers in
the sequence and swap them. Return the number of different final sequences that can be
obtained modulo 1,000,000,009.
Constraints
-N will be between 2 and 2000, inclusive.
-M will be between 0 and 2000, inclusive.
5 2012-10-31 20:39:25
Re: Timus 1930 (4 ответов, оставленных в Problems)
I realize this but got WA#11. I can't find my mistake.
Please help me.
#include <iostream>
#include <algorithm>
#include <list>
#define MAXV 10001
#define INF 1000000000
using namespace std;
typedef list<int> L;
struct Graph
{
L edges[2*(MAXV+1)];
int nvert;
}graph;
int parent[MAXV+1];
int distance_[MAXV+1];
bool svyaz[MAXV+1];
bool intree[MAXV+1];
void dijkstra(int start)
{
int weight,w,v,dist;
for(int i=1;i<=graph.nvert;i++)
{
distance_[i]=INF;
parent[i]=-1;
}
distance_[start]=0;
v=start;
while(intree[v]==false)
{
intree[v]=true;
if(svyaz[v]) weight=0;
else weight=1;
if(v==start) weight=0;
for(L::iterator i=graph.edges[2*v-1].begin();i!=graph.edges[2*v-1].end();i++)
{
w=*i;
if(distance_[w]>(distance_[v]+weight))
{
distance_[w]=distance_[v]+weight;
parent[w]=v;
svyaz[w]=true;
}
}
if(svyaz[v]) weight=1;
else weight=0;
if(v==start) weight=0;
for(L::iterator i=graph.edges[2*v].begin();i!=graph.edges[2*v].end();i++)
{
w=*i;
if(distance_[w]>(distance_[v]+weight))
{
distance_[w]=distance_[v]+weight;
parent[w]=v;
svyaz[w]=false;
}
}
v=1;
dist=INF;
for(int i=1;i<=graph.nvert;i++)
{
if((intree[i]==false)&&(dist>distance_[i]))
{
dist=distance_[i];
v=i;
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;
int a,b;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
graph.edges[2*a-1].push_back(b);
graph.edges[2*b].push_back(a);
}
graph.nvert=n;
int nach,kon;
cin>>nach>>kon;
if(nach==kon)
{
cout<<"0"; return 0;
}
dijkstra(nach);
cout<<distance_[kon];
return 0;
}
6 2012-10-31 12:56:53
Re: Timus 1930 (4 ответов, оставленных в Problems)
But problem with time.
This my code.
// timus1930.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <bitset>
#include <set>
#define MAXV 10001
using namespace std;
typedef vector<short> vi;
typedef bitset<MAXV+1> bits;
bits edges[MAXV+1];
int parent[MAXV+1];
bool visited[MAXV+1];
int n,m;
void BFS(int vertex)
{
queue <int> q;
q.push(vertex);
visited[vertex]=true;
while(!q.empty())
{
vertex=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(edges[vertex][i])
{
int vert=i;
if(visited[vert]==false)
{
visited[vert]=true;
parent[vert]=vertex;
q.push(vert);
}
}
}
}
}
int main()
{
int a,b;
scanf("%d %d",&n,&m);
set <int> *baland=new set<int>[n+1];
set <int> *past=new set<int>[n+1];
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
for(set <int>::iterator ite=past[a].begin();ite!=past[a].end();ite++)
{
past[b].insert(*ite);
}
past[b].insert(a);
for(set<int>::iterator ite=baland[b].begin();ite!=baland[b].end();ite++)
{
baland[a].insert(*ite);
}
edges[a][b]=true;
edges[b][a]=true;
}
int nach,kon;
cin>>nach>>kon;
if(nach==kon)
{
cout<<"0"; return 0;
}
BFS(nach);
int changes=0;
for(int i=kon;parent[i];i=parent[i],changes++);
changes--;
cout<<changes;
return 0;
}
7 2012-10-31 12:42:33
Тема: Timus 1930 (4 ответов, оставленных в Problems)
How can I quickly build adjacency matrix befor using bfs for this problem. I have TLE#6,#10,#12 for this problem. Any algorithm please!