# HackerEarth Decaying Roads problem solution

In this HackerEarth Decaying Roads problem solution There is a City having some set of roads where each road has the same source and the same destination.There are N trucks and M roads in the city.You are given K permits in the city(in the form of X and Y) which indicates that a truck X is permitted to travel on Road Y.

Each road has a restriction on the number of trucks it can allow to travel on it.This restricted number is known as Capacity[i].

Due to the poor condition of the roads, every year 1 particular road's capacity reduces by a number P. The data is known for Z years.

For each year before the reduction takes place,you need to predict the maximum number of trucks that can travel in the city.

## HackerEarth Decaying Roads problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long long intll n,m,lvl[4005],s,d,ptr[4005],con,avl[4005],ans[10005],q;struct edge{    ll a,b,cap,flow;};vector<edge>e;vector<pair<ll,ll> >pp,qry;vector<ll>v[4005];void init(){    ll i;    for(i=1;i<=4003;i++)    {        v[i].clear();        avl[i]=0;    }    for(i=1;i<=10000;i++)    {        ans[i]=0;    }    e.clear();    pp.clear();    qry.clear();}void add_edge(ll a,ll b,ll cap){    edge e1={a,b,cap,0};    edge e2={b,a,0,0};    v[a].push_back(e.size());  e.push_back(e1);  v[b].push_back(e.size());  e.push_back(e2);}bool bfs(){    ll i,j,k;    queue<ll>q;    q.push(s);    memset(lvl,-1,sizeof lvl);    lvl[s]=0;    while(!q.empty())    {        j=q.front();        q.pop();        for(k=0;k<v[j].size();k++)        {            ll id=v[j][k];            ll to=e[id].b;            if(lvl[to]==-1&&e[id].flow<e[id].cap)            {                lvl[to]=1+lvl[j];                q.push(to);            }        }    }    return (lvl[d]!=-1);}ll dfs(ll cur,ll flow){    ll i,j;    if(cur==d)    return flow;    for(;ptr[cur]<v[cur].size();ptr[cur]++)    {        ll id=v[cur][ptr[cur]];        ll to=e[id].b;        if(lvl[to]!=(1+lvl[cur])||(e[id].cap-e[id].flow<=0))        continue;        ll f=dfs(to,min(flow,e[id].cap-e[id].flow));        if(f>0)        {           e[id].flow+=f;           e[id^1].flow-=f;           return f;        }    }    return 0;}ll maxflow(){    ll total_flow=0,j;    while(bfs())    {        memset(ptr,0,sizeof ptr);        while(1)        {            if(j=dfs(s,10000000000000000))            {                total_flow+=j;            }            else            break;        }    }    return total_flow;}void flow_ans(){    ll i,j,k,x,y;    for(i=0;i<con;i++)    {        x=pp[i].first;        y=pp[i].second;        add_edge(x,n+y,1);    }    for(i=1;i<=n;i++)    {        add_edge(s,i,1);    }    vector<ll>eids;    for(i=1;i<=m;i++)    {        add_edge(i+n,d,avl[i]);        eids.push_back(e.size()-2);    }    ll prt=maxflow();    for(i=q-1;i>=0;i--)    {        x=qry[i].first;        y=qry[i].second;        e[eids[x-1]].cap+=y;        //cout<<e[eids[x-1]].a<<" "<<e[eids[x-1]].b<<" "<<e[eids[x-1]].cap<<"\n";        prt+=maxflow();        //cout<<prt<<"\n";        ans[i]=prt;    }    for(i=0;i<q;i++)    {        cout<<ans[i]<<"\n";    }}void solve(){    init();    ll i,j,ans,x,y;    cin>>n>>m>>con;    s=n+m+1;    d=n+m+2;    ans=0;    for(i=1;i<=con;i++)    {        cin>>x>>y;        pp.push_back({x,y});    }    for(i=1;i<=m;i++)    {        cin>>avl[i];    }    cin>>q;    for(i=1;i<=q;i++)    {        cin>>x>>y;        qry.push_back({x,y});        avl[x]-=y;    }    flow_ans();}int main(){    //freopen("samp.txt","r",stdin);    //freopen("sout.txt","w",stdout);    /*for(ll uu=0;uu<=9;uu++)    {        //string s=to_string(i);        //string s1=to_string(i);        stringstream ss;        ss << uu;        string s = ss.str();        string s1=ss.str();        s="in0"+s+".txt";        s1="out0"+s1+".txt";        freopen(s.c_str(),"r",stdin);        freopen(s1.c_str(),"w",stdout);*/        solve();    //}    return 0;}`

### Second solution

`#include<bits/stdc++.h>#define LL long long int#define M 1000000007#define endl "\n"#define eps 0.00000001LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}using namespace std;int cap[5001][5001];vector<int> graph[100001];int r[100001];int p[100001];int x[100001];int y[100001];int capacity[100001];vector<pair<int,int> > edges;bool flag = 0;bool visit[13000];void find_augmented(int cur, int t){    if(cur == t){         flag = 1;         return;    }    for(int i: graph[cur]){        if(visit[i] == 0){            if(cap[cur][i] > 0){                edges.push_back({cur , i});                visit[i] = 1;                find_augmented(i , t);                if(flag == 1){                    break;                }                edges.pop_back();            }        }    }    return;} int update_augmented(){    int mcap = cap[edges.back().first][edges.back().second];    for(int i = 0;i < edges.size(); i++){        mcap = min(mcap , cap[edges[i].first][edges[i].second]);    }    for(int i = 0; i < edges.size(); i++){        cap[edges[i].first][edges[i].second] -= mcap;        cap[edges[i].second][edges[i].first] += mcap;    }    return mcap;} int maxflow(int n,int s,int t){    int ans = 0;    memset(visit , 0 , sizeof(visit));    edges.clear();    while(1){        flag = 0;        find_augmented(s , t);        if(flag == 0)            break;        ans += update_augmented();        memset(visit , 0 , sizeof(visit));        edges.clear();    }    return ans;} int main()    {        ios_base::sync_with_stdio(0);        cin.tie(0);        int n , m , k;        cin >> n >> m >> k;        for(int i = 1; i <= n; i++){            graph[0].push_back(i);            graph[i].push_back(0);            cap[0][i] = 1;        }        for(int i = 1; i <= k; i++){            cin >> x[i] >> y[i];            graph[x[i]].push_back(n + y[i]);            graph[n + y[i]].push_back(x[i]);            cap[x[i]][n + y[i]] = 1;        }        for(int i = 1; i <= m; i++){            cin >> capacity[i];            graph[n + i].push_back(n + m + 1);            graph[n + m + 1].push_back(n + i);            cap[n + i][n + m + 1] = capacity[i];        }        int z;        cin >> z;        for(int i = 1; i <= z; i++){            cin >> r[i] >> p[i];            int idx = r[i];            cap[idx + n][n + m + 1] -= p[i];            assert(cap[idx + n][n + m + 1] >= 0);        }        int cur_flow = maxflow(n , 0 , n + m + 1);        vector<int> ans;        for(int i = z; i >= 1; i--){            int idx = r[i];            edges.clear();            memset(visit , 0 , sizeof(visit));            cap[idx + n][n + m + 1] += p[i];            while(1){                flag = 0;                edges.clear();                memset(visit , 0 , sizeof(visit));                find_augmented(0 , n + m + 1);                if(flag == 1)                    cur_flow += update_augmented();                else{                    assert(edges.size() == 0);                    break;                }            }            ans.push_back(cur_flow);        }        while(ans.size()){            cout << ans.back() << " " << endl;            ans.pop_back();        }    }`