### AFGhazy's blog

By AFGhazy, history, 8 years ago,

Why no one knows him or her till now; any one knows why ?! ?!

• +9

By AFGhazy, history, 8 years ago,

how can I free all the memory used by a trie ?!

• -1

By AFGhazy, history, 8 years ago,

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;
}
• -11

By AFGhazy, history, 8 years ago,

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.

• +32

By AFGhazy, history, 9 years ago,

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 )