![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
Moderator: Board moderators
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
*/