强大的dfs（用处1——拓扑排序【xdoj1025】,用处二——求强联通分量【ccf高速公路】）当然dfs用处多着咧

xdoj 1025

亮亮最近在玩一款叫做“梦想庄园”的经营游戏。在游戏中，你可以耕种，养羊甚至建造纺织厂。

如果你需要制造衣服，你首先得有布匹和毛线。布匹由棉花纺织而成；毛线由羊毛制成，而羊需要饲料才能长出羊毛，最终饲料由小麦和胡萝卜制成。

  假设游戏中共有N种物品，第i种物品由其他Ci个物品制成。亮亮需要你帮他制作M个任务物品来完成销售订单。

游戏中的每个物品都有一个价格Vi，当原材料不足以制作出所有的物品时，你需要花尽量少的钱买一些物品来完成任务。你可以选择直接购买所需的任务物品，也可以购买其他物品来制作任务物品，但是每制作一次需要W的代价。

 

题目分析：看着好吓人啊。。其实分析清晰也很简单。每种物体既可以直接买到或者由其他物体制作得到。那么我们就取两者的最小值。制作的花费我们可以这样求得
如果x的原材料有y 那么x和y之间有一条有向边 。然后按照拓扑排序的顺序自底而上求出各个物体制作所需的价值。。很简单吗？！

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int N=1e4+;

 vector < vector <int> > g(N);

 int val[N];

 bool vis[N];

 int n,m,w;

 void dfs (int rt) {

     vis[rt]=;

     if (g[rt].size()==) return ;// 最底层直接返回

     int cost=w;

     for (int i=;i<g[rt].size();i++) {

         int next=g[rt][i];

         if (!vis[next])  dfs(next);

         cost+=val[next];//cost制作费用

     }

     val[rt]=min (cost,val[rt]);//取两者最小值

     return ;

 }

 int main ()

 {

     int T;

     scanf ("%d",&T);

     while (T--) {

         scanf ("%d %d %d",&n,&m,&w);

         for (int i=;i<n;i++) g[i].clear();

         memset (vis,,sizeof(vis));

         for (int i=;i<n;i++) {

             scanf ("%d",&val[i]);

             int num; scanf ("%d",&num);

             for (int j=;j<num;j++) {

                 int u; scanf ("%d",&u);

                 g[i].push_back(u);

             }

         }

         for (int i=;i<n;i++)

             if (!vis[i])  dfs (i);

         int sum=;

         for (int i=;i<m;i++) {

             int x; scanf ("%d",&x);

             sum+=val[x];

         }

         printf ("%d\n",sum);

     }

     return ;

 }

ccf 高速公路 求联通分量 这个算法好像叫trajin 向这些科学家致敬

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <stack>

 #include <vector>

 using namespace std;

 const int N=1e4+;

 vector < vector <int> > g(N);

 stack <int> ss;

 bool instack[N];

 bool vis[N];

 int dfn[N],low[N];// dfn 保存遍历序号  low 这个点所能到达的最小点

 int ans;

 int n,m;

 int cnt;//访问顺序

 void dfs (int rt) {

     vis[rt]=;

     instack[rt]=; ss.push(rt);

     dfn[rt]=low[rt]=++cnt;

     for (int i=;i<g[rt].size();i++) {

         int next=g[rt][i];

         if (!vis[next]) {

             dfs (next);

             low[rt]=min (low[rt],low[next]);

         }

         else if (instack[next]) {

             low[rt]=min (low[rt],low[next]);

         }

     }

     if (dfn[rt]==low[rt]) {// dfn[rt]==low[rt] 表示遍历一个联通分变量啦

         int num=;

         int tmp=ss.top(); ss.pop(); instack[tmp]=;//在栈中 说明这个点的后继子孙还没有访问完

         while (dfn[tmp]!=low[tmp]) { num++; tmp=ss.top(); ss.pop(); instack[tmp]=;}

         ans+=(num-)*num/;

     }

     return ;

 }

 int main ()

 {

     ios::sync_with_stdio(false);

     cin>>n>>m;

     for (int i=;i<=m;i++) {

         int x,y; cin>>x>>y;

         g[x].push_back(y);

     }

     for (int i=;i<=n;i++)

         if (!vis[i]) dfs (i);

     printf ("%d\n",ans);

     return ;

 }