11045 - My T-shirt suits me

[zyz913614263]

I solved this problem using backtracking,it is very easy;

[nbacool2]

So I got the following code which is implementation of Edmond-Karp's Max flow algorithm. The thing I cannot understand is why my augmenting function returns a randomly huge number as pushed flow when it should be always 1. For example just before returning the minEdge, I print what is the value and I always get 1, but right after that I assign to a "flow" variable the result from the augmenting and it is always a huge random number when it should be the minEdge which is one. Any ideas how that's possibe? If you run the commented input you'll see what I'm talking about.

Code: Select all

//UVa problem 11045 - My T-shirt suits me
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<string, string> ss;
struct Edge {
       int to, capacity, reverseEdgeIndex;
       Edge(int _t, int _c, int _r)
       {
                to = _t;
                capacity = _c;
                reverseEdgeIndex = _r;
       }
};
const int MAXN = 200;
const int SOURCE = MAXN - 2;
const int SINK = MAXN - 1;
const int INF = 1000;
int N, M;
vector<ss> sizes;
vector<Edge> RG[MAXN];
vector<bool> answers;
int parent[MAXN], parentEdge[MAXN];
bool visited[MAXN];
int encode(const string &str)
{
    if(str == "L") return 0;
    else if(str == "XL") return 1;
    else if(str == "XXL") return 2;
    else if(str == "XS") return 3;
    else if(str == "M") return 4;
    else if(str == "S") return 5;
    cout<<"encode: "<<-1<<endl;
    return -1;
}
void construct()
{
     //connecting the source to all the types of T-Shirts
     for(int i = 0; i < 6; ++i)
     {
             RG[SOURCE].push_back(Edge(i, N/6, RG[i].size()));
             RG[i].push_back(Edge(SOURCE, 0, RG[SOURCE].size()-1));// adding a reverse edge
     }

     //connecting the T-Shirts to all the clients
     for(int i = 0; i < M; ++i)
     {
             int node1 = encode(sizes[i].first);
             int node2 = encode(sizes[i].second);
             cout<<"node1: "<<node1<<endl;
             cout<<"node2: "<<node2<<endl;
             RG[node1].push_back(Edge(6 + i, 1, RG[6 + i].size()));
             RG[6 + i].push_back(Edge(node1, 0, RG[node1].size()-1));// adding a reverse edge
             RG[node2].push_back(Edge(6 + i, 1, RG[6 + i].size()));
             RG[6 + i].push_back(Edge(node2, 0, RG[node2].size()-1));// adding a reverse edge

             //connecting the client with the sink
             RG[6+i].push_back(Edge(SINK, 1, RG[SINK].size()));
             RG[SINK].push_back(Edge(6+i, 0, RG[6+i].size()-1));//adding a reverse edge
     }
}
void BFS()
{
     memset(parent, -1, sizeof parent);
     memset(visited, 0, sizeof visited);
     queue<int> Q;
     Q.push(SOURCE);
     while(!Q.empty())
     {
           int current = Q.front(); Q.pop();
           for(int i = 0; i < RG[current].size(); ++i)
           {
                   int child = RG[current][i].to;
                   int capacity = RG[current][i].capacity;
                   if(!visited[child] && capacity > 0)
                   {
                            parent[child] = current;
                            visited[child] = true;
                            parentEdge[child] = i;
                            Q.push(child);
                            if(child == SINK) break;
                   }
           }
     }
}
int augment(int node, int minEdge)
{
    cout<<"minEdge: "<<minEdge<<endl;
    if(node == SOURCE) cout<<"returnMinEdge: "<<minEdge<<endl;
    if(node == SOURCE) return minEdge;
    if(node == SINK && parent[SINK] == -1) return 0;
    int flow = augment(parent[node], min(minEdge, RG[parent[node]][parentEdge[node]].capacity));
    RG[parent[node]][parentEdge[node]].capacity -= flow;
    RG[node][RG[parent[node]][parentEdge[node]].reverseEdgeIndex].capacity += flow;
}
bool maxFlowEdmondKarp()
{
     int maxFlow = 0;
     while(true)
     {
                BFS();
                int flow = augment(SINK, INF);
                cout<<"Flow is: "<<flow<<endl;
                maxFlow += flow;

                if(flow == 0) break;
     }
     cout<<"current MaxFlow: "<<maxFlow<<endl;
     return maxFlow == M;
}
void read()
{
 for(int i = 0; i < MAXN; ++i) RG[i].clear();
 sizes.clear();
 //all ready
 cin >> N >> M;
 for(int i = 0; i < M; ++i)
 {
         string s1, s2;
         cin >> s1 >> s2;
         sizes.push_back(ss(s1, s2));
 }
 construct();
 answers.push_back(maxFlowEdmondKarp());
}
int main()
{
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
            read();
    }
    for(int i = 0; i < T; ++i)
    {
            if(answers[i]) cout<<"YES";
            else cout<<"NO";
            cout<<'\n';
    }
    cout<<"THAT'S ALL FOLKS\n";
    return 0;
}
/*
3
18 6
L XL
XL L
XXL XL
S XS
M S
M L
6 4
S XL
L S
L XL
L XL
6 1
L M
*/

[brianfry713]

Your augment function isn't returning anything at the end.

[nbacool2]

Yeah, got AC after I returned the flow in the augment function.