bipartite matching
input
왼쪽 개수, 오른쪽 개수, edge수
각각의 edge는 왼쪽num -> 오른쪽 num
10 15 31
1 1
2 1
2 3
3 2
3 3
3 4
4 3
4 7
4 8
4 9
4 10
5 7
5 9
5 13
5 14
6 8
6 9
6 12
7 10
7 13
7 14
7 15
8 6
8 8
8 10
9 4
9 10
9 15
10 10
10 11
10 12
output
Max Flow is 10
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
struct node
{
int end;
int flow;
int cap;
struct node* next;
struct node* pair;
};
typedef struct node node;
int queue[1000];
int front;
int tail;
int pd[1000];
int pb[1000];
int visited[1000];
struct node* adj;
int v,e;
int n,m,edge;
node* insert_adj(int a, int b, int w,int c);
void dfs(int i);
int bfs(int i);
int inqueue(int a);
int dequeue();
int main(void)
{
int i,sum=0,j;
int num=0;
int startpoint;
struct node *temp1,*temp2;
FILE* fin = fopen("bipar_input2.txt","r");
node* t;
//fscanf (fin,"%d %d",&v,&e);
if (fin==NULL){
printf ("파일이없음\n");
exit(0);
}
fscanf (fin,"%d %d %d",&n,&m, &edge);
v=n+m;
adj = (node*)malloc(sizeof(node)*(v+3));
//adj = (node*)malloc(sizeof(node)*(n*n*2+2));
for (i=0;i<=v+2;i++){
adj[i].end=-1;
adj[i].flow=0;
adj[i].cap=0;
adj[i].next=NULL;
}
for (i=0;i<edge;i++)
{
int left,right;
fscanf (fin,"%d %d",&left, &right);
temp1 = insert_adj(0,left,0,1);
temp2 = insert_adj(left,0,0,0);
temp1->pair = temp2;
temp2->pair = temp1;
temp1 = insert_adj(left,n+right,0,1);
temp2 = insert_adj(n+right,left,0,0);
temp1->pair = temp2;
temp2->pair = temp1;
temp1 = insert_adj(n+right,v+1,0,1);
temp2 = insert_adj(v+1,n+right,0,0);
temp1->pair = temp2;
temp2->pair = temp1;
}
/*
for (i=0;i<e;i++)
{
struct node *temp1,*temp2;
fscanf (fin,"%d %d %d",&a,&b,&c);
temp1=insert_adj(a,b,0,c);
temp2=insert_adj(b,a,0,0);
temp1->pair = temp2;
temp2->pair = temp1;
//insert_adj(b,a,w);
}
*/
memset(visited,-1,sizeof(visited));
memset(pd,-1,sizeof(pd));
memset(pb,-1,sizeof(pb));
memset(visited,-1,sizeof(visited));
/*
for (int i=0;i<v;i++)
{
node* t=&adj[i];
while(t!=NULL)
{
printf ("<%d %d %d (%d)> ",i,t->end,t->cap,t->pair->cap);
t=t->next;
}
printf ("\n");
}
*/
while(1)
{
int minflow;
memset(visited,-1,sizeof(visited));
memset(queue,0,sizeof(queue));
front=tail=0;
inqueue(0);
minflow=bfs(0);
printf ("minflow : %d\n",minflow);
/*for (i=0;i<=v+2;i++)
{
printf ("%d ",pb[i]);
}
printf ("\n\n");*/
if ( visited[v+1] == -1 )
break;
else
{
int child = v+1;
int parent = pb[child];
node* t=&adj[child];
printf ("%d %d ",child,parent);
while (parent != 0)
{
t=&adj[parent];
while(t!=NULL){
if (t->end == child)
break;
t=t->next;}
t->flow += minflow;
t->pair->flow += -minflow;
child=parent;
parent = pb[child];
printf ("%d ",parent);
}
printf ("\n\n");
/*
while(t!=NULL){
if (t->end == parent)
break;
t=t->next;}
t->flow += -minflow;
t->pair->flow += +minflow;
*/
t=&adj[0];
while(t!=NULL){
if (t->end == child)
break;
t=t->next;}
t->flow += minflow;
t->pair->flow += -minflow;
}
}
node* temp = &adj[v+1];
while (temp!= NULL)
{
sum += temp->pair->flow;
temp = temp->next;
}
printf ("max flow is : %d\n",sum);
return 0;
}
node* insert_adj(int a, int b, int w,int c){
node* temp;
node* z;
if (adj[a].end == -1){
adj[a].end=b;
adj[a].flow=w;
adj[a].cap=c;
adj[a].next=NULL;
return &adj[a];
}
temp=&adj[a];
while(temp->next != NULL)
{
if (temp->end == b)
{
temp->cap=c;
return temp;
}
temp=temp->next;
}
if (temp->end == b)
{
temp->cap=c;
return temp;
}
z = (node*)malloc(sizeof(node));
z->end=b;
z->flow=w;
z->cap=c;
z->next=NULL;
temp->next=z;
return z;
}
int bfs(int i)
{
int z = dequeue();
int min=987654321;
while( z!=-987654321)
{
node* t = &adj[z];
while(t!=NULL &&t->end != -1)
{
if (t->cap-t->flow > 0 && visited[t->end] == -1)
{
//printf ("%d %d\n",t->end,t->cap - t->flow);
if (t->cap - t->flow <min)
min=t->cap-t->flow;
if (t->end == v+1){
visited[t->end] = 1;
pb[t->end]=z;
return min;
}
visited[t->end] = 0;
pb[t->end] = z;
inqueue(t->end);
}
t=t->next;
}
visited[z] = 1;
z=dequeue();
}
return min;
}
void dfs(int i)
{
if (visited[i] != -1)
return;
else
{
node* t=&adj[i];
visited[i]=1;
while( t!=NULL &&t->end != -1 )
{
if (visited[t->end] == -1){
pd[t->end]=i;
dfs(t->end);
}
t=t->next;
}
}
}
int inqueue(int a)
{
queue[tail++]=a;
return 0;
}
int dequeue()
{
if (front == tail)
return -987654321;
return queue[front++];
}