1.POJ 2186

题意：有n头牛和m个有向关系表示两个牛有暧昧关系，牛还都挺喜欢自己的，问你有多少牛是被全体喜欢的。

理解：一看到全体就知道要求两两可达的强连通分量，要是只有一个联通分量就说明每个牛都和其他牛暧昧，多余一个联通分量那就要看他们是不是连成串，穿成串那最后一个出度为0的就是牛中最high的牛群，但要是有个出度大于1或存在2个出度为0的联通分量，就没有那么好的牛了，所以Tarjan对图分析一遍，得到缩的点之间的出度关系。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MAXN = 100002;int in[MAXN], out[MAXN];vector
          
            G[MAXN];int dfn[MAXN],low[MAXN],belong[MAXN],belong_cnt[MAXN];int Count,n,m,cnt;bool instack[MAXN];stack 
           
            stap;void init(){ Count=cnt=0; memset(dfn,0,sizeof(dfn)); memset(belong,0,sizeof(belong)); memset(instack,0,sizeof(instack)); memset(belong_cnt,0,sizeof(belong_cnt));}void tarjan(int x){ int i; dfn[x]=low[x]=++cnt; stap.push(x); instack[x]=1; for(i=0;i
            
             1) printf("0\n"); else printf("%d\n", ans); } return 0;}
            
           
          
         
        
       
      

 

2.POJ 3020

题意：有些格子中的点，要我们用最少的可以覆盖两个相邻点的圈，覆盖所有的点。

理解：http://www.cnblogs.com/updateofsimon/p/3441343.html 最小路径覆盖问题，将每个点拆成两个点一左一右，相邻的点连线，求个最大匹配，每2个表示一种匹配，所以结果就是 点个数 - 最大匹配/2

#include 
      
       #include 
       
        #define MAXN 405int point[41][11];int G[MAXN][MAXN],link[MAXN],used[MAXN],n,m;bool path(int u) {    for(int i=1;i<=n;i++)        if(G[u][i] && !used[i]) {            used[i] = 1;            if(link[i]==-1 || path(link[i])) {                link[i] = u;                return true;            }        }    return false;}void hungary() {    int ans = 0;    memset(link,-1,sizeof(link));    for(int i=1;i<=n;i++) {        memset(used,0,sizeof(used));        if(path(i)) ans++;    }    printf("%d\n", n-ans/2);}int main() {    int T;    int x,y;    int dir[4][2]={
    0,-1,0,1,-1,0,1,0};    scanf("%d",&T);    while(T--) {        n = 0;        char ch;        scanf("%d%d",&x,&y);        memset(point,0,sizeof(point));        memset(G,0,sizeof(G));        for(int i = 0; i < x; i++) {            getchar();            for (int j = 0; j < y; j++) {                ch=getchar();                if (ch=='*')                    point[i][j] = ++n;            }        }        for (int i = 0; i < x; i++) {            for (int j = 0; j < y; j++) {                if(point[i][j])                    for (int d = 0; d < 4; d++)                        if(i+dir[d][0]>= 0 && i+dir[d][0] < x && j+dir[d][1] >= 0 && j+dir[d][1] < y)                            if(point[i+dir[d][0]][j+dir[d][1]])                            G[point[i][j]][point[i+dir[d][0]][j+dir[d][1]]] = 1;            }        }        hungary();    }    return 0;}