## 11045 - My T-shirt suits me

Moderator: Board moderators

zyz913614263
New poster
Posts: 3
Joined: Tue Oct 18, 2011 4:27 pm

### Re: 11045 - My T-shirt suits me      I solved this problem using backtracking,it is very easy;

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 11045 - My T-shirt suits me

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];
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;
}
{
for(int i = 0; i < MAXN; ++i) RG[i].clear();
sizes.clear();
cin >> N >> M;
for(int i = 0; i < M; ++i)
{
string s1, s2;
cin >> s1 >> s2;
sizes.push_back(ss(s1, s2));
}
construct();
}
int main()
{
int T;
cin >> T;
for(int i = 0; i < T; ++i)
{
}
for(int i = 0; i < T; ++i)
{
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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11045 - My T-shirt suits me

Your augment function isn't returning anything at the end.
Check input and AC output for thousands of problems on uDebug!

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

### Re: 11045 - My T-shirt suits me

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