最大流的应用,最小路径覆盖,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1422
/*距离标号的最大流*/
#include 
<stdio.h>

const int LEN = 500;

const int MAX = 0x7fffffff;

struct
{
    
int c;
    
int f;
}
map[LEN][LEN]; /*邻接矩阵*/

struct
{
    
int node;
}
nearl[LEN][LEN];/*邻接链表,第一个表示最后一个位置*/

void initm ( int n )
{
    
    
for ( int i=0; i<n; i++ )
    
{
        nearl[i][
0].node = 0;
        
for ( int j=0; j<n; j++ )
        
{
            map[i][j].c 
= map[i][j].f = 0;
        }

    }

}


int dis[LEN];//标号的数组

void initd ( int n )
{
    
    
for ( int i=0; i<n; i++ )
    
{
        dis[i] 
= -1;
    }

}


int que[LEN];
int head, tail;

void initq ()
{
    
    head 
= 0;
    tail 
= -1;
}


void inq ( int in )
{
    
    que[
++tail] = in;
}


void outq ( int *out )
{
    
    
*out = que[head++];
}


int testempty ()
{
    
    
return head > tail ? 1 : 0;
}


int mark ( int s, int t, int n )/*进行距离标号*/
{
    
    
int out;
    
int in;
    
    initd ( n );
    
    initq ();
    inq ( s );
    dis[s] 
= 0;
    
while ( ! testempty () )
    
{
        outq ( 
&out );
        
if ( out == t )
        
{
            
return 1;
        }

        
for ( int p=1; p<=nearl[out][0].node; p++ )
        
{
            in 
= nearl[out][p].node;
            
if ( map[out][in].c > map[out][in].f || map[in][out].f > 0 )
            
{
                
if ( dis[in] == -1 )
                
{
                    dis[in] 
= dis[out] + 1;
                    inq ( in );
                }

            }

        }

    }

    
return 0;
}


typedef struct
{
    
int now;
    
int from;
    
int weight;
}
type;
type stack[LEN];
//用于记录路径的堆栈
int top;

void inits ()
{
    
    top 
= -1;
}


void push ( type *in )
{
    
    top 
++;
    stack[top].now 
= in->now;
    stack[top].from 
= in->from;
    stack[top].weight 
= in->weight;
}


void pop ()
{
    top 
--;
}


int gettop ()
{
    
    
return stack[top].now;
}


int minest ( int a, int b )
{
    
    
return a < b ? a : b;
}


int ad ()/*流量调整函数*/
{
    
    
int now, from;
    
int min = MAX;
    
int i;
    
for ( i=1; i<=top; i++ )
    
{
        now 
= stack[i].now;
        from 
= stack[i].from;
        
if ( stack[i].weight > 0 )
        
{
            min 
= minest ( min, map[from][now].c-map[from][now].f );
        }

        
else
        
{
            min 
= minest ( min, map[now][from].f );
        }

    }

    
    
for ( i=1; i<=top; i++ )
    
{
        now 
= stack[i].now;
        from 
= stack[i].from;
        
if ( stack[i].weight > 0 )
        
{
            map[from][now].f 
+= min;
        }

        
else
        
{
            map[now][from].f 
-= min;
        }

    }

    
return min;
}


int maxflow ( int s, int t, int n )/*最小费用最大流函数*/
{
    
    
int p;
    
int i;
    
int flow = 0;    
    type in;
    
    
while ( mark ( s, t, n ) )
    
{
        inits ();
        in.now 
= s;
        in.from 
= -1;
        in.weight 
= 1;
        push ( 
&in );
        
while ( ( p = gettop () ) != t )
        
{
            
for ( i=1; i<=nearl[p][0].node; i++ )
            
{
                
int v = nearl[p][i].node;
                
if ( map[p][v].c > map[p][v].f )
                
{
                    
if ( dis[p] == dis[v] - 1 )
                    
{
                        in.now 
= v;
                        in.from 
= p;
                        in.weight 
= 1;
                        push ( 
&in );
                        
break;
                    }

                }

                
if ( map[v][p].f > 0 )
                
{
                    
if ( dis[p] == dis[v] - 1 )
                    
{
                        in.now 
= v;
                        in.from 
= p;
                        in.weight 
= -1;
                        push ( 
&in );
                        
break;
                    }

                }

            }

            
if ( i > nearl[p][0].node  )
            
{
                dis[p] 
= n;
                pop ();
            }

        }

        flow 
+= ad ();
    }

    
return flow;
}


void add ( int a, int b, int c )//增加一条边
{
    
    
if ( ! map[a][b].c && ! map[b][a].c )
    
{
        
int p = nearl[a][0].node;
        nearl[a][
++p].node = b;
        nearl[a][
0].node ++;
        p 
= nearl[b][0].node;
        nearl[b][
++p].node = a;
        nearl[b][
0].node ++;
    }

    map[a][b].c 
+= c;
}


int main ()
{

    
int t, n, m;
    
int b, e;

    
while ( scanf ( "%d"&t ) != EOF )
    
{
        
while ( t -- )
        
{
            scanf ( 
"%d%d"&n, &m );
            
            initm ( 
2 * n + 2 );

            
for ( int i=1; i<n+1; i++ )
            
{
                add ( 
0, i, 1 );
            }


            
for ( i=0; i<m; i++ )
            
{
                scanf ( 
"%d%d"&b, &e );

                add ( b, e
+n, 1 );
            }


            
for ( i=n+1; i<2*n+1; i++ )
            
{
                add ( i, 
2*n+11 );
            }


            printf ( 
"%d\n", n - maxflow ( 02*n+12*n+2 ) );
        }

    }

    
return 0;
}