问题 E: Plug It In!

时间限制: 12 Sec  内存限制: 128 MB
提交: 116  解决: 31
[提交] [状态] [命题人:admin]

题目描述

Adam just moved into his new apartment and simply placed everything into it at random. This means in particular that he did not put any effort into placing his electronics in a way that each one can have its own electric socket.
Since the cables of his devices have limited reach, not every device can be plugged into every socket without moving it first. As he wants to use as many electronic devices as possible right away without moving stuff around, he now tries to figure out which device to plug into which socket. Luckily the previous owner left behind a plugbar which turns one electric socket into 3. 
Can you help Adam figure out how many devices he can power in total?

 

输入

The input consists of:
• one line containing three integers m, n and k, where
– m (1 ≤ m ≤ 1 500) is the number of sockets;
– n (1 ≤ n ≤ 1 500) is the number of electronic devices;
– k (0 ≤ k ≤ 75 000) is the number of possible connections from devices to sockets.
• k lines each containing two integers xi and yi indicating that socket xi can be used to power device yi .
Sockets as well as electronic devices are numbered starting from 1.
The plugbar has no cable, i.e. if it is plugged into a socket it simply triples it.

 

输出

Output one line containing the total number of electrical devices Adam can power.

 

样例输入

复制样例数据

3 6 8
1 1
1 2
1 3
2 3
2 4
3 4
3 5
3 6

样例输出

5

题目大意:有n个插座与m个插头,给出插座与插头的匹配关系,然后你还可以使其中一个插座连接他可以连接的三个插头,问最多可以匹配多少对插头与插座

题目思路:

题目也就比较明显给出了二分图的性质,如果没有链接三个插头的插座那么可以直接匈牙利算法跑最大匹配,现在有了这个限制之后,我们完全可以根据匈牙利算法的性质,先跑一遍最大匹配,然后我们遍历每一个点,再给每一个点找两次匹配,这样就很容易OK了.唯一注意的是:每次都要还原初始的归属,因为对一个点进行再次寻找之后,可能会把另一个集合的归属给改变.

AC:

//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e9+7;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,b;
int head[maxn];
ll cnt=0;
struct node{
    int e,next;
}edge[maxn];
bool used[maxn];
int girl[maxn];
int save[maxn];
void restart()
{
    memset(head,-1,sizeof(head));
    memset(girl,0,sizeof(girl));
}
void addedge(int u,int v)
{
    edge[cnt]=node{v,head[u]};
    head[u]=cnt++;
}
bool Find(int x)
{
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        if(!used[edge[i].e])
        {
            used[edge[i].e]=true;
            if(!girl[edge[i].e]||Find(girl[edge[i].e]))
            {
                girl[edge[i].e]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    ll sum=0;
    restart();
    scanf("%lld%lld%lld",&n,&m,&b);
    for(int i=1;i<=b;i++)
    {
        ll x,y;scanf("%lld%lld",&x,&y);
        addedge(x,y);
    }
    ll maxl=0;
    for(int i=1;i<=n;i++)
    {
        for(int k=1;k<=m;k++) used[k]=false;
        if(Find(i)) sum++;
    }
    for(int i=1;i<=m;i++) save[i]=girl[i];
    for(int j=1;j<=n;j++)
    {
        ll temp=sum;
        for(int k=1;k<=m;k++) girl[k]=save[k];
        for(int k=1;k<=2;k++)
        {
            for(int i=1;i<=m;i++) used[i]=false;
            if(Find(j)) temp++;
            else break;
        }
        maxl=max(maxl,temp);
    }
    printf("%lld\n",maxl);
    return 0;
}
 
/**************************************************************
    Problem: 9655
    User: Qianwan069
    Language: C++
    Result: 正确
    Time:396 ms
    Memory:21628 kb
****************************************************************/

比赛时没有联想到这种思维,很遗憾....