10983 - Buy one, get the rest free

[double_zero]

I Keep Getting WA. could anybody help me by giving me a test case that breaks my code?

Code: Select all

#include <iostream>
#include <unistd.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <cmath>
#include <queue>
#include <sstream>
#define INF (int)1e9
#define MAX (400+10)
#define node(city,day) ((city)*d+(day))

using namespace std;

int n, m, d;

int res[MAX][MAX],RES[MAX][MAX],cap[MAX][MAX],CAP[MAX][MAX],cost[MAX][MAX],mf,f,s=0,t=1,par[MAX];
vector<int> dist,adj[MAX];

void agument(int v, int minEdge){
    if(v==s) f=minEdge;
    else if(par[v]!=-1){
        agument(par[v],min(minEdge,res[par[v]][v]));
        res[par[v]][v]-=f; res[v][par[v]]+=f;
        //cout << v << " ";
    }
}

void bfs(int s, int maxcost){
    memset(par,-1,sizeof par); dist.assign(MAX,INF);
    dist[s]=0; queue<int> q; q.push(s);
    while(!q.empty()){
        int u=q.front(); q.pop();
        //cout << "bfs: " << u << endl;
        if(u==t) break;
        for(int i=0 ; i<adj[u].size(); i++){
            int v=adj[u][i]; //cout << "->" << v << " cost: " << cost[u][v] << endl;
            if(res[u][v]>0 && dist[v]==INF && cost[u][v]<=maxcost){
                dist[v]=dist[u]+1; q.push(v); par[v]=u;
            }
        }
    }
}

int main(){
    int cs=1, tc; cin >> tc;
    while(tc--){ cin >> n >> d >> m; d++;
        //initilize
        memset(cost,0,sizeof cost);
        memset(RES,0,sizeof RES);
        memset(CAP,0,sizeof CAP);
        for(int i=0 ; i<n ; i++) adj[i].clear();
        s = node(n,d); t = node(n-1,d-1);
        //cout << s << " " << t << endl;
        //parse input and constracting the graph
        //(u,e) =c=> (v,e+1)
        int u,v,c,p,e;
        while(m--){
            cin >> u >> v >> c >> p >> e; u--; v--;
            RES[node(u,e)][node(v,e+1)]+=c; //RES[v][u]+=c;
            CAP[node(u,e)][node(v,e+1)]+=c; //CAP[v][u]+=c;
           cost[node(u,e)][node(v,e+1)] =p;
            adj[node(u,e)].push_back(node(v,e+1)); //adj[v].push_back(u);
        }
        //source =Zi=> (0,i)
        int zi,zs=0;
        for(int i=0 ; i<n ; i++){
            cin >> zi; zs+=zi;
            RES[s][node(i,0)]+=zi; //RES[v][u]+=c;
            CAP[s][node(i,0)]+=zi; //CAP[v][u]+=c;
           cost[s][node(i,0)] =0;
            adj[s].push_back(node(i,0)); //adj[v].push_back(u);
        }
        //(u,d) =inf=> (u,d+1)
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<d-1 ; j++){
                RES[node(i,j)][node(i,j+1)]+=INF; //RES[v][u]+=c;
                CAP[node(i,j)][node(i,j+1)]+=INF; //CAP[v][u]+=c;
               cost[node(i,j)][node(i,j+1)] =0;
                adj[node(i,j)].push_back(node(i,j+1)); //adj[v].push_back(u);
            }
        }
        //binary search + max flow
        int lo=0, hi=100001, mid;bool hasAns=0;
        while(lo<hi){
            mid = (lo+hi)/2;
            //cout << "mid: " << mid << " ";
            memcpy(res,RES,sizeof RES);
            memcpy(res,CAP,sizeof CAP);mf=0;
            while(1){
                f=0; bfs(s,mid);
                agument(t,INF); //cout << endl;
                if(f==0) break;
                mf+=f;
            }
            //cout << "mf: " << mf << endl;
            if(mf==zs) hi=mid, hasAns=1; else lo=mid+1;
        }
        if(!hasAns) printf("Case #%d: Impossible\n", cs++);
        else printf("Case #%d: %d\n", cs++, hi );
    }
    return 0;
}