2013
12-23

# Jimmy’s Assignment

Jimmy is studying Advanced Graph Algorithms at his university. His most recent assignment is to find a maximum matching in a special kind of graph. This graph is undirected, has N vertices and each vertex has degree 3. Furthermore, the graph is 2-edge-connected (that is, at least 2 edges need to be removed in order to make the graph disconnected). A matching is a subset of the graph’s edges, such that no two edges in the subset have a common vertex. A maximum matching is a matching having the maximum cardinality.
Given a series of instances of the special graph mentioned above, find the cardinality of a maximum matching for each instance.

The first line of input contains an integer number T, representing the number of graph descriptions to follow. Each description contains on the first line an even integer number N (4<=N<=5000), representing the number of vertices. Each of the next 3*N/2 lines contains two integers A and B, separated by one blank, denoting that there is an edge between vertex A and vertex B. The vertices are numbered from 1 to N. No edge may appear twice in the input.

For each of the T graphs, in the order given in the input, print one line containing the cardinality of a maximum matching.

2
4
1 2
1 3
1 4
2 3
2 4
3 4
4
1 2
1 3
1 4
2 3
2 4
3 4

2
2

hungary算法

#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=5001;
vector<int> g[MAXN];
int uN,vN;  //u,v数目
bool used[MAXN];
bool dfs(int u)
{
int v;
for(int i=0;i<g[u].size();i++)
{v=g[u][i];
if(!used[v])
{
used[v]=true;
{
return true;
}
}
}
return false;
}
int hungary()
{
int res=0;
int u;
for(u=1;u<=uN;u++)
{
memset(used,0,sizeof(used));
if(dfs(u))  res++;
}
return res;
}
int main()
{
int t,n,i,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<=n;i++)
g[i].clear();
for(i=0;i<n*3/2;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
uN=n;
printf("%d\n",hungary()/2);
}
return 0;
}

Hopcroft-Carf算法

#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=5001;
const int INF=1<<28;
vector<int> g[MAXN];
int Mx[MAXN],My[MAXN],Nx,Ny;
int dx[MAXN],dy[MAXN],dis;
bool vst[MAXN];
bool searchP()
{
queue<int> Q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=1;i<=Nx;i++)
if(Mx[i]==-1)
{
Q.push(i);
dx[i]=0;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(dx[u]>dis)
break;
for(int i=0;i<g[u].size();i++)
if(dy[g[u][i]]==-1)
{
int v=g[u][i];
dy[v]=dx[u]+1;
if(My[v]==-1)
dis=dy[v];
else
{
dx[My[v]]=dy[v]+1;
Q.push(My[v]);
}
}
}
return dis!=INF;
}
bool DFS(int u)
{
for(int i=0;i<g[u].size();i++)
if(!vst[g[u][i]]&&dy[g[u][i]]==dx[u]+1)
{
int v=g[u][i];
vst[v]=1;
if(My[v]!=-1&&dy[v]==dis)
continue;
if(My[v]==-1||DFS(My[v]))
{
My[v]=u;
Mx[u]=v;
return 1;
}
}
return 0;
}
int MaxMatch()
{
int res=0;
memset(Mx,-1,sizeof(Mx));
memset(My,-1,sizeof(My));
while(searchP())
{
memset(vst,0,sizeof(vst));
for(int i=1;i<=Nx;i++)
if(Mx[i]==-1&&DFS(i))
res++;
}
return res;
}
int main()
{
int t,n,i,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
g[i].clear();
for(i=0;i<n*3/2;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
Nx=n;Ny=n;
printf("%d\n",MaxMatch()/2);
}
return 0;
}

#include<stdio.h>

int main()
{
int t,n,i,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n*3/2;i++)
scanf("%d%d",&x,&y);
printf("%d\n",n/2);
}
return 0;
}

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}