Skip to main content

Posts

Showing posts from January, 2011

Successive shortest paths algorithm description with source

• Start with flow f with f ( u,v )=0 for all u , v . • repeat until value( f ) = r – Find the shortest path P in G f from s to t – Let q be the minimum residual capacity of an edge on P. – Send min( q , r – value( f )) additional units of flow across P. On the successive shortest paths algorithm : • May use exponential running time • Assume G has no negative edge costs. • Gives optimal answer. – Invariant: f   has minimum cost among all flows with value value ( f ). • Suppose we obtain f’ from f  by sending across P. • Let f’’ be a minimum cost flow with same value as f’ . • Write f’’ – f as weighted sum of paths from s to t in G f and circuits in G f . Argue that cost( f’ – f ) / cost( f’’ – f ), using that: – P is shortest path – Circuits have non-negative costs, by optimality of f .   Source code link is given  here

Minimum cost Maxflow or mincut maxflow or Successive Shortest Path source code in C++

when there is need of minimum cost along with maximum flow then comes this problem. Sometimes it called successive shortest path . Here is a problem for better understanding 10498 ************************************************************************************* #include<iostream> #include<string> #include<vector> #include<queue> #include<algorithm> using namespace std; #define MV 102 typedef long long LL; LL  cst[MV][MV],     cap[MV][MV],     par[MV],dis[MV],     source,sink,flow; vector<int>adj[MV]; struct pq{     LL d,n;     void ini(LL a,LL b){n=a;d=b;}     bool operator<(const pq &b)const{return d>b.d;} }; bool PFS(int s,int sk) {     priority_queue<pq>Q;     pq u,v;     int i;     memset(dis,50,sizeof dis);     di...

Basic Maxflow or Network Flow source code in c++

When there is one source and one sink and prospect is that to send maximum unit to sink then comes the need of maxflow.It is normally a bfs which helps to find the maximum capacity  over the line load and reduce this capacity from load until the load comes to zero.I mean until there is any path from source to sink. Here is the code for maxflow.Hope it help.  #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<iostream> #include<queue> #include<algorithm> using namespace std; #define INF  2147483647 /***************** Max Flow Algorithm*************** ****************************************************/ const int maxINDX=102; int flow[maxINDX][maxINDX],cap[maxINDX][maxINDX]; int path[maxINDX]; int src,dest; int BFS(int node) {     int i,item,cf;     queue<int> q;     for(i=1;i<=node;i++)       ...

ACM problem submit in Java with BigInteger in uva online judge

When to use : • First of all in c,c ++ we have some problem with Big number Like 2^32 or more.This problem Can be solved by using c,c ++ ,but it is more easy or faster to use Java here. • Because Java support BigInteger And BigDecimal in java.math.BigInteger library. • Sometimes we have to generate number series like Fibonacci upto 1000.It is more easy in java to generate these without C.Where C or c++ is more complex. • Note: When time is factor it is not right to use java Library to use: • Import java.io.*; • Import java.math.BigInteger; • Import java.math.BigDecimal; • Import java.util.*; Taking Input: • For taking input Try to use Scanner. • Because it handle all space and newline itself. • Format: Scanner in = new Scanner(new BufferedReader (new InputStreamReader ( System.in ))); It will take input from Commandline . Use while( in.hasNext ())  to take every input from file or input line. After that you have to take it as BigI...

Summary of a Search Engine Conference Presentation

Summary of a Search Engine: Abstract Today web has become larger with its own prospect.Every Day about 500 hundreds of new website is added to Internet.So it is rapidly increasing.These new web has new information and new element that an indivisual need.But it is not possible to learn or find any particular element from these sites where every sites may have avarage of 100 pages.Where comes the need of search.So from the prospect it is looklike that the search must be efficient and also the memory of storing these info is also need to be compromized.Here comes the choice of good search engine.So how and what makes a search engine different from other we will deal with it. Key word  : 1.Page Ranking 2. Probability 3. Anchor Text 4.Vector Space model. 5.Doc. Indexing. 6.Metadata. 7.Lexicon 8.Hitlist 9.Barrels 10.Parsing 1). Page Ranking: As search engine is developed the information may found in several web pa...