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 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();
}
}
0 Comments