優化1：求最大匹配時候先能匹配就匹配上。
優化2：標記已經確定不是必要點的行和列 flag[]和flag2[]
注意1：刪除匹配邊后 應在匹配邊的兩面點 分別查詢
注意2：沒查到新匹配要還原匹配邊
#include<stdio.h>
#include<string.h>
const int size2 = 100110;
const int size1 = 10110;
int n , m , k ;
struct node{
node *p;
node *q;
int v;
int v2;
};
int val;
node edg[size2];
bool visit[size1];
int pp[size1];
bool flag[size1];
bool flag2[size1];
node *g[size1];
node *g1[size1];
int ppre[size1];
int ppr[size1];
int nxy[size1];
inline bool check(int x , int y , int fc){
node *now = g[x];
while(now != NULL){
if(now->v == y){
if(fc == 0)
return true;
if(fc == 1){
now->v = -1;
return true;
}
if(fc == 2){
now->v = val;
return true;
}
}
else{
now = now->p;
}
}
return false;
}
inline bool check2(int x , int y , int fc){
node *now = g1[x];
while(now != NULL){
if(now->v2 == y){
if(fc == 0)
return true;
if(fc == 1){
now->v2 = -1;
return true;
}
if(fc == 2){
now->v2 = val;
return true;
}
}
else{
now = now->q;
}
}
return false;
}
inline bool find(int a){
node *now = g[a];
while(now != NULL){
int i = now->v;
if(i != -1){
if(!visit[i] ){
visit[i] = true;
if(pp[i] == -1 ||find(pp[i])){
pp[i] = a;
nxy[a] = i;
return true;
}
}
}
now = now->p;
}
return false;
}
inline bool find2(int a){
node *now = g1[a];
while(now != NULL){
int i = now->v2;
if(i != -1){
if(!visit[i] ){
visit[i] = true;
if(nxy[i] == -1 ||find2(nxy[i])){
nxy[i] = a;
pp[a] = i;
return true;
}
}
}
now = now->q;
}
return false;
}
void output(){
printf("\n\n");
for( int i = 1 ; i <= m ; i++)
printf("%d -> %d\n",pp[i],i);
printf("\n");
for( int i = 1 ; i <= n ; i++)
printf("%d -> %d\n",i,nxy[i]);
printf("\n\n");
}
void output1(int x){
node *now = g1[x];
while(now != NULL){
int i = now->v2;
printf(" %d",i);
now = now->q;
}
printf("\n");
}
int main(){
int a1,i,a2;
int _case = 0;
int num;
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
num = 0;
memset(g,0,sizeof(g));
memset(g1,0,sizeof(g1));
memset(pp,-1,sizeof(pp));
memset(nxy,-1,sizeof(nxy));
for(i = 1; i <= k ; i++){
scanf("%d%d",&a1,&a2);
if(check(a1,a2,0)) continue;
edg[i].v = a2;
edg[i].v2 = a1;
edg[i].p = NULL;
edg[i].q = NULL;
if(g[a1] == NULL){
g[a1] = &edg[i];
}else{
edg[ppre[a1]].p = &edg[i];
}
if(g1[a2] == NULL){
g1[a2] = &edg[i];
}else{
edg[ppr[a2]].q = &edg[i];
}
ppre[a1] = i ;
ppr[a2] = i ;
if(pp[a2] == -1 && nxy[a1] == -1){
pp[a2] = a1;
nxy[a1] = a2;
num++;
}
}
for(i = 1 ; i <= m ; i++){
if(pp[i] == -1){
memset(visit,0,sizeof(visit));
if(find2(i)){
num++;
}
}
}
memset(flag,0,sizeof(flag));
memset(flag2,0,sizeof(flag2));
int ans = 0;
for(i = 1 ; i <= m ; i++){
if(pp[i] != -1){
int key = 0;
int now = pp[i];
pp[i] = -1 ;
nxy[now] = -1;
if(flag[pp[i]] == 0){
check(now,i,1);
memset(visit,0,sizeof(visit));
if(find(now)){
key = 1;
}
val = i ;
check(now,-1,2);
}
if(flag2[i] == 0 && key == 0 ){
check2(i,now,1);
memset(visit,0,sizeof(visit));
if(find2(i)){
key = 1;
}
val = now ;
check2(i,-1,2);
}
if(!key){
ans++;
nxy[now] = i;
pp[i] = now;
}
else{
flag[now] = 1 ;
flag2[i] = 1 ;
}
}//右側有邊
}
printf("Board %d have %d important blanks for %d chessmen.\n",++_case,ans,num);
}
return 0;
}