// C++ implementation of Hopcroft Karp algorithm for
// maximum matching
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define NIL 0
#define INF INT_MAX
int yos[5001];
// A class to represent Bipartite graph for Hopcroft
// Karp implementation
class BipGraph
{
// m and n are number of vertices on left
// and right sides of Bipartite Graph
int m, n;
// adj[u] stores adjacents of left side
// vertex 'u'. The value of u ranges from 1 to m.
// 0 is used for dummy vertex
list<int> *adj;
// These are basically pointers to arrays needed
// for hopcroftKarp()
int *pairU, *pairV, *dist;
public:
BipGraph(int m, int n); // Constructor
void addEdge(int u, int v); // To add edge
// Returns true if there is an augmenting path
bool bfs();
// Adds augmenting path if there is one beginning
// with u
bool dfs(int u);
// Returns size of maximum matcing
int hopcroftKarp();
};
// Returns size of maximum matching
int BipGraph::hopcroftKarp()
{
// pairU[u] stores pair of u in matching where u
// is a vertex on left side of Bipartite Graph.
// If u doesn't have any pair, then pairU[u] is NIL
pairU = new int[m+1];
// pairV[v] stores pair of v in matching. If v
// doesn't have any pair, then pairU[v] is NIL
pairV = new int[n+1];
// dist[u] stores distance of left side vertices
// dist[u] is one more than dist[u'] if u is next
// to u'in augmenting path
dist = new int[m+1];
// Initialize NIL as pair of all vertices
for (int u=0; u<m; u++)
{pairU[u] = NIL;
yos[u]=NIL;}
for (int v=0; v<n; v++)
pairV[v] = NIL;
// Initialize result
int result = 0;
// Keep updating the result while there is an
// augmenting path.
while (bfs())
{
// Find a free vertex
for (int u=1; u<=m; u++)
// If current vertex is free and there is
// an augmenting path from current vertex
if (pairU[u]==NIL && dfs(u))
result++;
}
return result;
}
// Returns true if there is an augmenting path, else returns
// false
bool BipGraph::bfs()
{
queue<int> Q; //an integer queue
// First layer of vertices (set distance as 0)
for (int u=1; u<=m; u++)
{
// If this is a free vertex, add it to queue
if (pairU[u]==NIL)
{
// u is not matched
dist[u] = 0;
Q.push(u);
}
// Else set distance as infinite so that this vertex
// is considered next time
else dist[u] = INF;
}
// Initialize distance to NIL as infinite
dist[NIL] = INF;
// Q is going to contain vertices of left side only.
while (!Q.empty())
{
// Dequeue a vertex
int u = Q.front();
Q.pop();
// If this node is not NIL and can provide a shorter path to NIL
if (dist[u] < dist[NIL])
{
// Get all adjacent vertices of the dequeued vertex u
list<int>::iterator i;
for (i=adj[u].begin(); i!=adj[u].end(); ++i)
{
int v = *i;
// If pair of v is not considered so far
// (v, pairV[V]) is not yet explored edge.
if (dist[pairV[v]] == INF)
{
// Consider the pair and add it to queue
dist[pairV[v]] = dist[u] + 1;
Q.push(pairV[v]);
}
}
}
}
// If we could come back to NIL using alternating path of distinct
// vertices then there is an augmenting path
return (dist[NIL] != INF);
}
// Returns true if there is an augmenting path beginning with free vertex u
bool BipGraph::dfs(int u)
{
if (u != NIL)
{
list<int>::iterator i;
for (i=adj[u].begin(); i!=adj[u].end(); ++i)
{
// Adjacent to u
int v = *i;
// Follow the distances set by BFS
if (dist[pairV[v]] == dist[u]+1)
{
// If dfs for pair of v also returns
// true
if (dfs(pairV[v]) == true)
{
pairV[v] = u;
pairU[u] = v;
yos[u]=v;
return true;
}
}
}
// If there is no augmenting path beginning with u.
dist[u] = INF;
return false;
}
return true;
}
// Constructor
BipGraph::BipGraph(int m, int n)
{
this->m = m;
this->n = n;
adj = new list<int>[m+1];
}
// To add edge from u to v and v to u
void BipGraph::addEdge(int u, int v)
{
adj[u].push_back(v); // Add u to v’s list.
}
// Driver Program
int main()
{
int n;
cin>>n;
string kal,zal;
cin>>kal>>zal;
BipGraph g(kal.size(), kal.size());
for (int i = 0; i < kal.size(); ++i)
{
for (int j = 0; j < kal.size(); ++j)
{
if(kal[i]!=zal[j])
{
g.addEdge(j+1,i+1);
}
}
}
g.hopcroftKarp();
string ans;
for (int i = 1; i <= kal.size(); ++i)
{
//debug(yos[i]);
ans.push_back(kal[yos[i]-1]);
}
cout<<ans;
return 0;
}
Compilation message
igra.cpp: In function 'int main()':
igra.cpp:196:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < kal.size(); ++i)
~~^~~~~~~~~~~~
igra.cpp:198:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < kal.size(); ++j)
~~^~~~~~~~~~~~
igra.cpp:208:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i <= kal.size(); ++i)
~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
396 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
1144 KB |
Output isn't correct |
| 8 |
Incorrect |
152 ms |
21240 KB |
Output isn't correct |
| 9 |
Runtime error |
138 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
138 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
