题意：二分图最大匹配问题。
解法1：匈牙利算法。
解法2：最大流。
添加原点s和汇点t。
设二分图左边的点集为X，添加从s 到X（1,2,....,m ）的边，权值为1；
右边的点集为Y，添加从Y（n-m+1, n-m+1, .... , n）到t 的边，权值为1；
田间X和Y之间的边。
求最大流。我用Dinic。最大流就是最大匹配。 配对保存在flow[i][j]中。
#include <fstream>
#include <memory.h>
using namespace std;
const int MAX = 300;
const int INF = 0x7FFFFFFF;
class Tadj
{
public:
int cnt;
int to[MAX];
Tadj(){
cnt=0;
}
void ins(int k){
to[++cnt]=k;
}
};
class Tqueue{
private:
long first, last, size;
long list[MAX*MAX];
public:
Tqueue(){
reset();
}
void reset(){
first=1, last=0, size=0;
}
void push_back(int k){
++size;
list[++last]=k;
}
void pop_front(){
size--;
first++;
}
long front(){
return list[first];
}
bool empty(){
return size==0;
}
};
class Tstack{
public:
int stack[MAX];
int top, min, p;
Tstack(){
reset();
}
void reset(){
top=0, min=INF;
}
void pop(){
top--;
}
void push(int k){
stack[++top]=k;
}
};
ifstream fin("input.txt");
ofstream fout("output.txt");
Tqueue Q;
Tstack S;
Tadj adj[MAX];
int s,t,c1,c2,m,n,maxflow;
int level[MAX], set[MAX];
int dist[MAX][MAX], odist[MAX][MAX], flow[MAX][MAX];
bool used[MAX];
inline void insert(int u, int v, int cost){
adj[u].ins(v);
dist[u][v]=cost;
}
void input(){
int i,u,v;
fin>>m>>n;
s=0, t=n+1;
for(i=1; i<=m; ++i){
insert(s, i, 1);
insert(i, s, 0);
}
for(i=n-m+1; i<=n; ++i){
insert(i, t, 1);
insert(t, 1, 0);
}
fin>>u>>v;
while(u!=-1 && v!=-1){
insert(u, v, 1);
insert(v, u, 0);
fin>>u>>v;
}
adj[t].cnt=0;
memcpy(odist, dist, sizeof(dist));
}
void Dinic_Level(){
Q.reset();
memset(used, 0, sizeof(used));
memset(level, 0, sizeof(level));
Q.push_back(s);
while(!Q.empty()){
int u = Q.front();
Q.pop_front();
used[u]=true;
for(int i=1; i<=adj[u].cnt; ++i){
int v = adj[u].to[i];
if(!dist[u][v]) continue;
if(used[v] || v==s) continue;
level[v] = level[u]+1;
Q.push_back(v);
}
}
}
void Dinic_Argument(){
S.stack[0]=s;
for(int i=1; i<=S.top; ++i){
int u = S.stack[i-1];
int v = S.stack[i];
if(dist[u][v]<S.min){
S.min = dist[u][v];
S.p = u;
}
}
for(int j=S.top; j>=1; --j){
int u = S.stack[j-1];
int v = S.stack[j];
flow[u][v] += S.min;
dist[u][v] -= S.min;
dist[v][u] += S.min;
}
}
bool Dinic_dfs(int u){
int outdegree=0;
if(u!=t){
for(int i=1; i<=adj[u].cnt; ++i){
int v = adj[u].to[i];
if(level[v]==level[u]+1 && dist[u][v]){
outdegree++;
S.push(v);
bool f = Dinic_dfs(v);
S.pop();
if(f && u!=S.p)
return true;
}
}
if(outdegree==0)
level[u]=0;
}else{
Dinic_Argument();
return true;
}
return false;
}
void Dinic(){
memset(flow, 0, sizeof(flow));
for( ; ; ){
Dinic_Level();
if(level[t]==0)
return;
S.reset();
Dinic_dfs(s);
}
}
long max_flow(){
long ret = 0;
for(int i=1; i<=n*2; ++i)
ret += flow[s][i];
return ret;
}
void solve(){
int cnt = 0;
Dinic();
maxflow = max_flow();
}
void output(){
fout<<maxflow<<endl;
for(int i=1; i<=m; ++i)
for(int j=n-m+1; j<=n; ++j){
if(flow[i][j]==1)
fout<<i<<" "<<j<<endl;
}
}
int main(){
input();
solve();
output();
return 0;
}
posted on 2011-02-24 12:35
小阮 阅读(758)
评论(0) 编辑 收藏 引用 所属分类:
数据结构和算法