xdoj 1025
亮亮最近在玩一款叫做“梦想庄园”的经营游戏。在游戏中，你可以耕种，养羊甚至建造纺织厂。
如果你需要制造衣服，你首先得有布匹和毛线。布匹由棉花纺织而成；毛线由羊毛制成，而羊需要饲料才能长出羊毛，最终饲料由小麦和胡萝卜制成。
假设游戏中共有N种物品，第i种物品由其他Ci个物品制成。亮亮需要你帮他制作M个任务物品来完成销售订单。
游戏中的每个物品都有一个价格Vi，当原材料不足以制作出所有的物品时，你需要花尽量少的钱买一些物品来完成任务。你可以选择直接购买所需的任务物品，也可以购买其他物品来制作任务物品，但是每制作一次需要W的代价。
题目分析：看着好吓人啊。。其实分析清晰也很简单。每种物体既可以直接买到或者由其他物体制作得到。那么我们就取两者的最小值。制作的花费我们可以这样求得
如果x的原材料有y 那么x和y之间有一条有向边 。然后按照拓扑排序的顺序自底而上求出各个物体制作所需的价值。。很简单吗？！
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 const int N=1e4+7; 8 vector < vector <int> > g(N); 9 int val[N]; 10 bool vis[N]; 11 int n,m,w; 12 void dfs (int rt) { 13 vis[rt]=1; 14 if (g[rt].size()==0) return ;// 最底层直接返回 15 int cost=w; 16 for (int i=0;i<g[rt].size();i++) { 17 int next=g[rt][i]; 18 if (!vis[next]) dfs(next); 19 cost+=val[next];//cost制作费用 20 } 21 val[rt]=min (cost,val[rt]);//取两者最小值 22 return ; 23 } 24 int main () 25 { 26 int T; 27 scanf ("%d",&T); 28 while (T--) { 29 scanf ("%d %d %d",&n,&m,&w); 30 for (int i=0;i<n;i++) g[i].clear(); 31 memset (vis,0,sizeof(vis)); 32 for (int i=0;i<n;i++) { 33 scanf ("%d",&val[i]); 34 int num; scanf ("%d",&num); 35 for (int j=0;j<num;j++) { 36 int u; scanf ("%d",&u); 37 g[i].push_back(u); 38 } 39 } 40 for (int i=0;i<n;i++) 41 if (!vis[i]) dfs (i); 42 int sum=0; 43 for (int i=0;i<m;i++) { 44 int x; scanf ("%d",&x); 45 sum+=val[x]; 46 } 47 printf ("%d ",sum); 48 } 49 return 0; 50 }
ccf 高速公路 求联通分量 这个算法好像叫trajin 向这些科学家致敬
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <stack> 5 #include <vector> 6 using namespace std; 7 const int N=1e4+7; 8 vector < vector <int> > g(N); 9 stack <int> ss; 10 bool instack[N]; 11 bool vis[N]; 12 int dfn[N],low[N];// dfn 保存遍历序号 low 这个点所能到达的最小点 13 int ans; 14 int n,m; 15 int cnt;//访问顺序 16 void dfs (int rt) { 17 vis[rt]=1; 18 instack[rt]=1; ss.push(rt); 19 dfn[rt]=low[rt]=++cnt; 20 for (int i=0;i<g[rt].size();i++) { 21 int next=g[rt][i]; 22 if (!vis[next]) { 23 dfs (next); 24 low[rt]=min (low[rt],low[next]); 25 } 26 else if (instack[next]) { 27 low[rt]=min (low[rt],low[next]); 28 } 29 } 30 if (dfn[rt]==low[rt]) {// dfn[rt]==low[rt] 表示遍历一个联通分变量啦 31 int num=1; 32 int tmp=ss.top(); ss.pop(); instack[tmp]=0;//在栈中 说明这个点的后继子孙还没有访问完 33 while (dfn[tmp]!=low[tmp]) { num++; tmp=ss.top(); ss.pop(); instack[tmp]=0;} 34 ans+=(num-1)*num/2; 35 } 36 return ; 37 } 38 int main () 39 { 40 ios::sync_with_stdio(false); 41 cin>>n>>m; 42 for (int i=1;i<=m;i++) { 43 int x,y; cin>>x>>y; 44 g[x].push_back(y); 45 } 46 for (int i=1;i<=n;i++) 47 if (!vis[i]) dfs (i); 48 printf ("%d ",ans); 49 return 0; 50 }