Since my solution got AC, there IS a limit on k... or the tests are too weak.

If you are using Edmonds-Karp, chnage it to regular Ford-Fulkerson (do DFS instead of BFS), because the running time in this case is better that way, as the maximum flow can be 1000 at most, so the complexity will be O(V*|f|) <= 2000*1.000.000 and this umber fits in 0.5 seconds. However, in case of E-K, the worst case running time is O(V^2*E) <= 1.000.000 * 1.000.000, which is the case of 1000-1000 complete graph and this exceeds the given 0.5 seconds.

Нужно убрать максимальное количество ребёр, но чтобы все вершины имели ненулевую степень.

I think that this problem should be solved with bipartite matching. But the fastest algo for this is O(sqrt(V)*E).

Firstly, the problem asks to find number of edges in minimum edge cover
Secondly, the number of such edges plus the number of maximum matching equals to number of vertices, that is N + M
Thirdly, you can find the number of max. matching easily with dfs-like algorithm (you can find code online).

The answer is N + M - (number of max. matching)

#include <iostream>
#include <vector>
#include <set>
using namespace std;
set < pair <int, int> > S;
set < pair <int, int> > :: iterator it;
vector <int> A[1111], B[1111];
int n, k, m, x[1111], y[1111], res, X[1111], Y[1111];
bool used[111111];
void cut_x(int v){
    for (int i = 0; i < k; i ++){
        if(!used[i] && X[i] == v && y[Y[i]] > 1){used[i] = true; y[Y[i]] --; res --;}
    }
}
void cut_y(int v){
    for (int i = 0; i < k; i ++){
        if(!used[i] && Y[i] == v && x[X[i]] > 1){used[i] = true; x[X[i]] --; res --;}
    }
}
int main(){
    cin >> n >> m >> k;
    res = k;
    for (int i = 0; i < k; i ++){
        int u, v;
        cin >> X[i] >> Y[i];
        A[X[i]].push_back(Y[i]);
        B[Y[i]].push_back(X[i]);
        x[X[i]] ++; y[Y[i]] ++;
    }
    for (int i = 1; i <= n; i ++)
        S.insert(make_pair(x[i], i));
    for (it = S.begin(); it != S.end(); it ++){
        pair <int, int> v = *it;
        if(v.first == 1){
            cut_y(A[v.second][0]);
        }else{
            cut_x(v.second);
        }
    }
    cout << res;
}

Find maximal matching using Kuhn algo.  Then greedily add missing connections.
That is slow way.
My C++ solution without any STL use runs in 230-240 ms.

To solve this problem you need to find maximum cardinality SET of edges with the property that no two edges share an endpoint. It can be done using Hopcroft-Karp algorithm. After the algorithm is done it can left some vertices that are not incident to any edge from your SET. Add one edge for each of them.

Also is there anyone who solved it using Ford-Fulkerson algorithm? I personally have TL, solving it that way.

Why i'm getting WA#1?

#include<bits/stdc++.h>
using namespace std;

int capacities[2002][2002];
int flowPassed[2002][2002];
vector<int> graph[2002];
int parentsList[2002];
int currentPathCapacity[2002];

int bfs(int startNode, int endNode)
{
    memset(parentsList, -1, sizeof(parentsList));
    memset(currentPathCapacity, 0, sizeof(currentPathCapacity));

    queue<int> q;
    q.push(startNode);

    parentsList[startNode] = -2;
    currentPathCapacity[startNode] = 999;

    while(!q.empty())
    {
        int currentNode = q.front();
        q.pop();

        for(int i=0; i<graph[currentNode].size(); i++)
        {
            int to = graph[currentNode][i];
            if(parentsList[to] == -1)
            {
                if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
                {
                    parentsList[to] = currentNode;
                    currentPathCapacity[to] = min(currentPathCapacity[currentNode],
                    capacities[currentNode][to] - flowPassed[currentNode][to]);
                    if(to == endNode)
                    {
                        return currentPathCapacity[endNode];
                    }
                    q.push(to);
                }
            }
        }
    }
    return 0;
}

int edmondsKarp(int startNode, int endNode)
{
    int maxFlow = 0;
      while(true)
    {
        int flow = bfs(startNode, endNode);
        if (flow == 0)
        {
            break;
        }
        maxFlow += flow;
        int currentNode = endNode;
        while(currentNode != startNode)
        {
            int previousNode = parentsList[currentNode];
            flowPassed[previousNode][currentNode] += flow;
            flowPassed[currentNode][previousNode] -= flow;
            currentNode = previousNode;
        }
    }
    return maxFlow;
}

int main()
{
    long int m,n,k,x;

    cin>>m>>n>>k;
    x=m+n;
    for(int i=0;i<k;i++)
    {
        int a,b;
        cin>>a>>b;
        graph[a].push_back(m+b);
        graph[m+b].push_back(a);
        capacities[a][m+b]=1;
    }
    for(int i=0;i<m;i++) {graph[0].push_back(i+1);capacities[0][i+1]=1;}
    for(int i=0;i<n;i++) {graph[m+i+1].push_back(x+1);capacities[m+i+1][x+1]=1;}
    int y=edmondsKarp(0,x+1);
    int p=(m-y+1)/2;
    p=p+(n-y+1)/2;
    cout<<(y+p)<<endl;

}

WA1 why?can i get the test data?

Edited by author 31.08.2015 18:13

Pls tell me what does author of this problem mean..
If all delegates are in different rooms then we can't use less than 4 connections to achieve the goal in sample input. What 3 connections can we use to do it?
Do we need all M pairs to be in answer?
I still can't solve it because statement is too loose for me.

3 3 9
1 1
1 2
1 3
2 1
3 1
2 2
2 3
3 2
3 3
answer:
3

I've tried a solution usind a matching algorithm and my answer is match + every_node that is not part of the match and I have WA. Can someone explain me how to do this problem?

LE: I got it! Never mind!

Edited by author 09.09.2013 21:06

#include <iostream>
#include <vector>

using namespace std;

int M, N;

int A[30001];
int B[30001];

vector < pair <int, int> > edges;

int main()
{
    cin >> M >> N;
    int K;
    cin >> K;
    for (int i = 0; i < K; i++)
    {
        int a, b;
        cin >> a >> b;
        edges.push_back(make_pair(a, b));
        A[a]++;
        B[b]++;
    }
    int count = 0;
    for (int i = 0; i < edges.size(); i++)
    {
        if (A[edges[i].first] > 1 && B[edges[i].second] > 1)
        {
            count++;
            A[edges[i].first]--;
            B[edges[i].second]--;
        }
    }
    cout << K - count << endl;
    return 0;
}

Could someone provide me with a test case? Each test from the discussion list passes ok. But still WA2.

Edited by author 20.12.2012 00:01

5 5 11
1 1
2 1
2 2
3 1
3 2
4 3
4 4
5 2
5 3
5 4
5 5

5 5 11
1 1
2 1
2 2
3 1
3 2
4 3
4 4
5 1
5 3
5 4
5 5

5 5 12
1 1
2 1
2 2
3 1
3 2
4 3
4 4
5 1
5 2
5 3
5 4
5 5

5 5 12
1 1
2 1
2 2
3 1
3 2
4 3
4 4
5 1
5 2
5 3
5 4
5 5

------------
Correct answers:
6
6
6
6

My program output:
5
5
5
5

var
  i,j,k,l,m,n,x,y,Ans:longint;
  a:array[1..2000,1..2000]of boolean;
  v:array[1001..2000]of boolean;
  opp:array[1..2000]of longint;
function find(x:longint):boolean;
  var
    i:longint;
  begin
    for i:=1001to 1000+m do begin
      if (not v[i])and(a[x][i])
         then begin
           v[i]:=true;
           if (opp[i]=0)or(find(opp[i]))
              then begin
                opp[i]:=x;exit(true);
              end;
         end;
    end;
    exit(false);
  end;
begin
  readln(n,m,x);Ans:=0;
  for i:=1to x do begin
    readln(j,k);
    a[j][k+1000]:=true;//a[k+n][j]:=false;
  end;
  for i:=1to n do begin
    fillchar(v,sizeof(v),false);
    if find(i)then inc(Ans);
  end;
  writeln(n+m-Ans);
end.

For every vertex choose at least one partner, preferably the one who has no pair yet, and select this edge.

Try to find a path that alternatively contains selected and unselected edges, such that it starts and ends on the same side and each end of the path belongs to at least two selected edges. Flip selected/unselected segments on the path thus reducing the number of selected edges by one.

Btw, to avoid any code duplication one may represent the graph as a four-dimensional array: [which delegation][selected or unselected][vertex index][index of the partner].