Why no one knows him or her till now; any one knows why ?! ?!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Why no one knows him or her till now; any one knows why ?! ?!
how can I free all the memory used by a trie ?!
Hey Codeforces, I have question in this problem my code run as follow:
run Dijkstra to get the shortest path
run Dijkstra again to see if any edge get to the destination with cost > shortest_path then cancel this edge
run max flow with vertex split
why this approach is wrong ?! thanks in advance.
this is my code :
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000;
int n,m;
int g[105][105], cost;
int dijkstra(int source){
vector<int > dist(105, INF);
dist[source] = 0;
set<pair<int, int > > q;
q.insert(make_pair(0, source));
while(!q.empty()){
int current = q.begin()->second;
int distance = q.begin()->first;
q.erase(q.begin());
if(current == n-1) return distance;
for(size_t i = 0; i < n; ++i)
{
if(g[current][i] + distance < dist[i]){
if(q.count(make_pair(dist[i], i))) q.erase(make_pair(dist[i], i));
dist[i] = g[current][i] + distance;
q.insert(make_pair(dist[i], i));
}
}
}
return dist[n-1];
}
void dijkstrA(int source){
vector<int > dist(105, INF);
dist[source] = 0;
set<pair<int, int > > q;
q.insert(make_pair(0, source));
while(!q.empty()){
int current = q.begin()->second;
int distance = q.begin()->first;
q.erase(q.begin());
for(size_t i = 0; i < n; ++i)
{
//cout << distance << " " << g[current][i] << " " << current << " " << i << endl,
if(g[current][i] + distance > cost && i == n-1) g[current][i] = INF;
if(g[current][i] + distance < dist[i]){
if(q.count(make_pair(dist[i], i))) q.erase(make_pair(dist[i], i));
dist[i] = g[current][i] + distance;
q.insert(make_pair(dist[i], i));
}
}
}
}
int c[205][205];
int flow[205][205];
int bottleneck[205];
int pre[205];
void build()
{
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(g[i][j] < INF) c[i*2+1][j * 2] = INF;//, cout << i << " " << j << endl;
}
}
}
int maxflow(){
int ans = 0;
for(int i = 0; i <= 100; ++i) c[i*2][i*2+1] = 1;
c[0][1] = INF;
c[2*(n-1)][2*(n-1)+1] = INF;
int S = 0, T = 2*(n-1)+1;
while(1){
memset(bottleneck, 0, sizeof bottleneck);
bottleneck[0] = INF;
queue<int > q; q.push(0);
while(!q.empty()&&!bottleneck[T]){
int cur = q.front(); q.pop();
for(int i = S; i <= T; i++){
if(!bottleneck[i]&&c[cur][i] > flow[cur][i]){
q.push(i);
pre[i] = cur;
bottleneck[i] = min(bottleneck[cur], c[cur][i] - flow[cur][i]);
}
}
}
if(bottleneck[T] == 0) break;
for (int cur = T; cur != 0; cur = pre[cur]) {
flow[pre[cur]][cur] += bottleneck[T];
flow[cur][pre[cur]] -= bottleneck[T];
}
ans += bottleneck[T];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
for(int i = 1,a,b,c; i <= m; ++i)
{
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min(c,g[a][b]);
g[b][a] = min(c,g[b][a]);
}
cost = dijkstra(0);
dijkstrA(0);
build();
cost = maxflow();
if(cost == INF) cout << "IMPOSSIBLE" << endl;
else cout << cost << endl;
return 0;
}
Hey, Codeforces I suffered for awhile from writing efficient codes for binary searching, but recently I found an efficient way using bit masking. Say you want to maximize a result using binary search and good function that return true if it's oky or false otherwise. so our binary search would be like that:
__int64 r = 0; for(int i = 62; i >= 0; --i) { if( good(r + (1LL<<i)) ) r += (1LL<<i); }
now you can binary search with out usage of variables such as low and high and middle which would lead to infinite loops.
I understood where the formula n / 2 * ( R2 ) * sin(2 * \pi / n)
but I couldn't understand why n = pi / gcd( of the three angles in the given triangle )
thanks in advance.
http://mirror.codeforces.com/contest/445/problem/C
can any one explain the problem and the answer for me ? the tutorial and the problem statement are so mysterious for me thanks in advance.
Название |
---|