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


HackerEarth Decaying Roads problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll 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.00000001
LL 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();
}
}