Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <deque>
- #include <cmath>
- #define INF 10000
- using namespace std;
- struct person{
- string name, skill;
- int rank;
- person(string Name, string Skill, int Rank){
- name = Name; skill = Skill; rank = Rank;
- }
- };
- vector <person> data;
- vector <vector <int> > g;
- const int MAXN = 2003;
- int c[MAXN][MAXN], f[MAXN][MAXN];
- int N;
- void readData(int &n){
- cin >> n;
- N = 2 * n + 2;
- data.resize(n+1,person("0","0",0));
- g.resize(N+1);
- for (int i=1; i<=n; i++){
- cin >> data[i].name;
- cin >> data[i].skill;
- cin >> data[i].rank;
- }
- }
- void buildNetwork(int& n){
- for (int i=1; i<=n; i++){
- for (int j=1; j<=n; j++){
- if (abs(data[i].rank - data[j].rank) == 2 && (data[i].skill == "anything" || data[j].skill == "anything" ||
- (data[i].skill == "statements" && data[j].skill == "testdata") || (data[i].skill == "testdata" && data[j].skill == "statements"))){
- g[i].push_back(j + n);
- g[j + n].push_back(i);
- c[i][j + n] = 1;
- }
- }
- }
- for (int i=1; i<=n; i++){
- g[N-1].push_back(i);
- g[i].push_back(N-1);
- c[N-1][i] = 1;
- }
- for (int i=n+1; i<=2*n; i++){
- g[i].push_back(N);
- g[N].push_back(i);
- c[i][N] = 1;
- }
- }
- bool bfs(int v, deque <int>& turn, vector <int>& lvl){
- int q,to;
- for (q=0; q<g[v].size(); q++){
- to = g[v][q];
- if (c[v][to] - f[v][to] > 0 && lvl[to] == INF){
- lvl[to] = lvl[v] + 1;
- turn.push_back(to);
- }
- }
- turn.pop_front();
- if (!turn.empty()) bfs(*turn.begin(),turn,lvl);
- return lvl[N] != INF;
- }
- int dfs(int v, vector <int>& pointer, vector <int>& lvl){
- if (v == N){
- return 1;
- }
- int q,to;
- for (q=pointer[v]; q<g[v].size(); q++){
- to = g[v][q];
- if (lvl[v] + 1 == lvl[to] && c[v][to] - f[v][to] > 0 && dfs(to,pointer,lvl)){
- f[v][to] += 1;
- f[to][v] -= 1;
- return 1;
- }
- else{
- pointer[v]++;
- }
- }
- return 0;
- }
- void findMaxFlow(int &n){
- deque <int> turn;
- vector <int> lvl(N+1);
- vector <int> pointer(N+1);
- while (1){
- turn.push_back(N-1);
- lvl.assign(N+1,INF);
- lvl[N-1]=0;
- if (!bfs(N-1,turn,lvl)) break;
- pointer.assign(N+1,0);
- while (dfs(N-1,pointer,lvl));
- }
- int pairs = 0;
- for (int i=1; i<=n; i++){
- for (int j=n+1+i; j<=2*n; j++){
- if (f[i][j] == 1){
- pairs++;
- }
- }
- }
- cout << pairs << "\n";
- for (int i=1; i<=n; i++){
- for (int j=n+1+i; j<=2*n; j++){
- if (f[i][j] == 1){
- if (data[i].skill != "testdata" && data[j - n].skill != "statements") cout << data[i].name << " " << data[j - n].name << "\n";
- else cout << data[j - n].name << " " << data[i].name << "\n";
- }
- }
- }
- }
- int main(){
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- int n;
- readData(n);
- buildNetwork(n);
- findMaxFlow(n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment