2013
12-23

# Summer Holiday

To see a World in a Grain of Sand
And a Heaven in a Wild Flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
―― William Blake

12 16
2 2 2 2 2 2 2 2 2 2 2 2
1 3
3 2
2 1
3 4
2 4
3 5
5 4
4 6
6 4
7 4
7 12
7 8
8 7
8 9
10 9
11 10

3 6

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<math.h>
#define N 1010
#define inf 10000000
using namespace std;
inline int Min(int a,int b){return a>b?b:a;}

struct node{
int from, to, nex;
}edge[N*5];
edge[ edgenum ] = E;
}
int DFN[N], Low[N], Time, vis[N], sign, belong[N];
int Stack[N], top;
void tarjan(int u, int fa){
DFN[ u ] = Low[ u ] = Time++;
vis[ u ] = 1;
Stack[top++] = u;
int child = 0;
for(int i = head[u]; i!=-1; i = edge[i].nex){
int v = edge[i].to;
if(DFN[ v ] == -1){
tarjan(v, u);
Low[u] = Min(Low[u], Low[v]);
}
/*else if(fa == v){
if(child) Low[u] = Min(Low[u], DFN[v]);
child++;
}*/
else if(vis[v])//v是走过的点 -> 这是反向弧
Low[u] = Min(Low[u], DFN[v]);
}
if(DFN[u] == Low[u])//反向弧在u及u以下
{
sign++;
while(1){
int now = Stack[--top];
vis[now] = 0;
belong[now] = sign;
if(now == u)break;
}
}
}

void tarjan_init(){
memset(DFN, -1, sizeof(DFN));
memset(Low, -1, sizeof(Low));
//		memset(belong, 0, sizeof(belong));
memset(vis, 0, sizeof(vis));
sign = top = 0;
Time = 0;
}
int a[N], n, m;
int lala[N], inde[N];

int main(){
int i,j,u,v;
while(~scanf("%d %d",&n,&m)){
tarjan_init();

for(i=1;i<=n;i++)scanf("%d",&a[i]);
while(m--){
scanf("%d %d",&u,&v);
}
for(i=1;i<=n;i++)if(DFN[i]==-1)tarjan(i, -1);

int ans1 = 0, ans2 = 0;
memset(inde, 0, sizeof(inde));
for(i = 0;i<edgenum; i++)
{
u = edge[i].from; v = edge[i].to;
if(belong[u] != belong[v])
inde[ belong[v] ] ++;
}
for(i = 1; i <= sign;i++)
{
if(inde[i] == 0)
ans1++;
lala[i] = inf;
}
for(i = 1; i <= n;i++)
{
int tmp = belong[i];
if(inde[ tmp ] == 0)
lala[tmp] = Min(lala[tmp], a[i]);
}
for(i = 1; i <= sign; i++)
if(lala[i] != inf)
ans2 += lala[i];

printf("%d %d\n",ans1,ans2);
}
return 0;
}

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。