对多校赛的题目，我深感无力。题目看不懂，英语是能懂的，题目具体的要求以及需要怎么做没有头绪。样例怎么来的都不明白。好吧，看题解吧。
http://www.cnblogs.com/kane0526/archive/2013/07/21/3203992.html
题目大意：
把一幅有向图中的点最少可以划分为几个区域。划分的规则是：1、可以互相到达的点必须在同一区域。2、每个城市都必须被划分。3、对于属于同一区域中的任意两点，要么满足u->v,要么满足v->u。
第三条规则需要着重解释一下。对于测试数据1->2,1->3，因为2与3之间没有边，所以2与3必须被划为2个区域。所以答案是2。
做法：
建图求强连通（Tarjan算法），然后对得到的DAG，重新建图。遍历每条边，不属于同一连通分支的点就连一条边。正向图和反向图都可以。
最后答案就是SCC - ans。SCC 是连通分支数，ans是最大匹配数。因为这里求的最小路径覆盖。
最小路径覆盖 = 顶点数 - 最大匹配数
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8 const int N =5010, M=100010,INF=0x3f3f3f3f;; 9 struct node 10 { 11 int to, next; 12 }edge[M]; 13 int head[N], low[N], dfn[N], sta[N], belg[N], num[N]; 14 bool vis[N]; 15 int scc,index,top, tot; 16 void tarbfs(int u) 17 { 18 int i,j,k,v; 19 low[u]=dfn[u]=++index; 20 sta[top++]=u; 21 vis[u]=1; 22 for(i=head[u];i!=-1;i=edge[i].next) 23 { 24 v=edge[i].to; 25 if(!dfn[v]) 26 { 27 tarbfs(v); 28 if(low[u]>low[v]) low[u]=low[v]; 29 } 30 else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v]; 31 } 32 if(dfn[u]==low[u]) 33 { 34 scc++; 35 do 36 { 37 v=sta[--top]; 38 vis[v]=0; 39 belg[v]=scc; 40 num[scc]++; 41 } 42 while(v!=u) ; 43 } 44 } 45 void Tarjan(int n) 46 { 47 memset(vis,0,sizeof(vis)); 48 memset(dfn,0,sizeof(dfn)); 49 memset(num,0,sizeof(num)); 50 memset(low,0,sizeof(low)); 51 index=scc=top=0; 52 for(int i=1;i<=n;i++) 53 if(!dfn[i]) tarbfs(i); 54 } 55 void init() 56 { 57 tot=0; 58 memset(head,-1,sizeof(head)); 59 } 60 void addedge(int i,int j) 61 { 62 edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++; 63 } 64 int cx[N],cy[N],dx[N],dy[N]; 65 bool bmask[N]; 66 int nx,dis,ans; 67 vector<int> bmap[N]; 68 bool searchpath() 69 { 70 queue<int> q; 71 dis=INF; 72 memset(dx,-1,sizeof(dx)); 73 memset(dy,-1,sizeof(dy)); 74 for(int i=1;i<=nx;i++) 75 { 76 if(cx[i]==-1){ q.push(i); dx[i]=0; } 77 while(!q.empty()) 78 { 79 int u=q.front(); q.pop(); 80 if(dx[u]>dis) break; 81 for(int i=0;i<bmap[u].size();i++) 82 { 83 int v=bmap[u][i]; 84 if(dy[v]==-1) 85 { 86 dy[v]= dx[u] + 1; 87 if(cy[v]==-1) dis=dy[v]; 88 else 89 { 90 dx[cy[v]]= dy[v]+1; 91 q.push(cy[v]); 92 } 93 } 94 } 95 } 96 } 97 return dis!=INF; 98 } 99 int findpath(int u) 100 { 101 for(int i=0;i<bmap[u].size();i++) 102 { 103 int v=bmap[u][i]; 104 if(!bmask[v]&&dy[v]==dx[u]+1) 105 { 106 bmask[v]=1; 107 if(cy[v]!=-1&&dy[v]==dis) continue; 108 if(cy[v]==-1||findpath(cy[v])) 109 { 110 cy[v]=u; cx[u]=v; 111 return 1; 112 } 113 } 114 } 115 return 0; 116 } 117 void maxmatch() 118 { 119 ans=0; 120 memset(cx,-1,sizeof(cx)); 121 memset(cy,-1,sizeof(cy)); 122 while(searchpath()) 123 { 124 memset(bmask,0,sizeof(bmask)); 125 for(int i=1;i<=nx;i++) 126 if(cx[i]==-1) ans+=findpath(i); 127 } 128 } 129 int main() 130 { 131 //freopen("test.txt","r",stdin); 132 int cas,i,j,k,n,m; 133 scanf("%d",&cas); 134 while(cas--) 135 { 136 scanf("%d%d",&n,&m); 137 init(); 138 while(m--) 139 { 140 scanf("%d%d",&i,&j); 141 addedge(i,j); 142 } 143 Tarjan(n); 144 for(i=1;i<=n;i++) bmap[i].clear(); 145 for(i=1;i<=n;i++) 146 { 147 for(k=head[i];k!=-1;k=edge[k].next) 148 { 149 j=edge[k].to; 150 if(belg[i]!=belg[j]) bmap[belg[j]].push_back(belg[i]); 151 } 152 } 153 nx=scc; 154 maxmatch(); 155 printf("%d ",scc-ans); 156 } 157 return 0; 158 }