关键词:
题目连接:
https://www.luogu.com.cn/problem/P2853
题意:
有n个奶牛在不同牧场,牧场之间有m条路。
求所以奶牛都能共同到达的牧场的数量
思路:
dfs每一个奶牛可以到的牧场。
开一个d[N]数组记录d[i] i这个牧场能来的奶牛的个数,如果d[i]==n,就符合题意。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int N=101000;
vector<int> p[N];
int n,m,k;
int ans;
int a[N];
int d[N];
bool st[N];
void dfs(int u)
// if(p[u].size()==0) return ;
// printf("u===%d \\n",u);
d[u]++;
st[u]=true;
for(int i=0;i<p[u].size();i++)
int t=p[u][i];
// printf("u===%d t===%d \\n",u,t);
if(!st[t])
// d[t]++;
dfs(t);
int main()
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
while(k--)
int x,y;
cin>>x>>y;
p[x].push_back(y);
// p[y].push_back(x);
for(int i=1;i<=n;i++)
memset(st,0,sizeof(st));
dfs(a[i]);
for(int i=1;i<=m;i++)
// printf("d[%d]==%d \\n",i,d[i]);
if(d[i]==n)
ans++;
cout<<ans<<endl;
```
洛谷p2853[usaco06dec]牛的野餐cowpicnic
题目描述Thecowsarehavingapicnic!EachofFarmerJohn‘sK(1≤K≤100)cowsisgrazinginoneofN(1≤N≤1,000)pastures,convenientlynumbered1...N.ThepasturesareconnectedbyM(1≤M≤10,000)one-waypaths(no 查看详情
洛谷p2853[usaco06dec]cowpicnics题解(代码片段)
题目连接:https://www.luogu.com.cn/problem/P2853题意:有n个奶牛在不同牧场,牧场之间有m条路。求所以奶牛都能共同到达的牧场的数量思路:dfs每一个奶牛可以到的牧场。开一个d[N]数组记录d[i]i这个牧场能来的奶牛的个... 查看详情
洛谷p2852[usaco06dec]牛奶模式milkpatterns
题目描述FarmerJohnhasnoticedthatthequalityofmilkgivenbyhiscowsvariesfromdaytoday.Onfurtherinvestigation,hediscoveredthatalthoughhecan‘tpredictthequalityofmilkfromonedaytothenext,therearesomeregularpattern 查看详情
p2853[usaco06dec]牛的野餐cowpicnic(代码片段)
-------------------------长时间不写代码了,从学校中抽身出来真的不容易啊------------------------链接:Miku-----------------------这道题的思路就在于建反图,如果每一头牛都能到达的话,那么在反图上,这个点也一定能到达每一头牛。那... 查看详情
洛谷p2851[usaco06dec]最少的硬币thefewestcoins(完全背包+多重背包)(代码片段)
题目描述FarmerJohnhasgonetotowntobuysomefarmsupplies.Beingaveryefficientman,healwayspaysforhisgoodsinsuchawaythatthesmallestnumberofcoinschangeshands,i.e.,thenumberofcoinsheusestopayplusthenumberofcoinshe 查看详情
洛谷p2850[usaco06dec]虫洞wormholes题解
此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置。题目链接:https://www.luogu.org/problem/show?pid=2850【题目描述】John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你... 查看详情
洛谷p2850[usaco06dec]虫洞wormholes判负环
虫洞(wormhole)FJ在农场上闲逛时,发现他的农场里有很多虫洞。虫洞是一条特殊的有向路径,当FJ从它的一头走到另一头后,他将被传送到过去的某个时刻。FJ的每个农场包括N(1<=N<=500)块按1..N编号的草地、M(1<=M<=2500)条... 查看详情
bzoj1648/p2853[usaco06dec]牛的野餐cowpicnic(代码片段)
P2853[USACO06DEC]牛的野餐CowPicnic你愿意的话,可以写dj。然鹅,对一个缺时间的退役选手来说,暴力模拟是一个不错的选择。让每个奶牛都把图走一遍,显然那些被每个奶牛都走过的点就是符合条件的点。1#include<iostream>2#include&... 查看详情
洛谷p3004[usaco10dec]宝箱treasurechest
P3004[USACO10DEC]宝箱TreasureChest题目描述BessieandBonniehavefoundatreasurechestfullofmarvelousgoldcoins!Beingcows,though,theycan‘tjustwalkintoastoreandbuystuff,soinsteadtheydecidetohavesomefunwiththecoins. 查看详情
洛谷p3004[usaco10dec]宝箱treasurechest
P3004[USACO10DEC]宝箱TreasureChest题目描述BessieandBonniehavefoundatreasurechestfullofmarvelousgoldcoins!Beingcows,though,theycan‘tjustwalkintoastoreandbuystuff,soinsteadtheydecidetohavesomefunwiththecoins. 查看详情
洛谷——p2872[usaco07dec]道路建设buildingroads
P2872[USACO07DEC]道路建设BuildingRoads题目描述FarmerJohnhadjustacquiredseveralnewfarms!Hewantstoconnectthefarmswithroadssothathecantravelfromanyfarmtoanyotherfarmviaasequenceofroads;roadsalreadyconnectsomeoft 查看详情
洛谷p2868[usaco07dec]观光奶牛sightseeingcows
P2868[USACO07DEC]观光奶牛SightseeingCows题目描述FarmerJohnhasdecidedtorewardhiscowsfortheirhardworkbytakingthemonatourofthebigcity!Thecowsmustdecidehowbesttospendtheirfreetime.Fortunately,theyhaveadetailedcit 查看详情
洛谷p2922[usaco08dec]秘密消息secretmessage
P2922[USACO08DEC]秘密消息SecretMessage题目描述Bessieisleadingthecowsinanattempttoescape!Todothis,thecowsaresendingsecretbinarymessagestoeachother.Evertheclevercounterspy,FarmerJohnhasinterceptedthefirst 查看详情
洛谷p2926[usaco08dec]拍头pattingheads
P2926[USACO08DEC]拍头PattingHeads题目描述It‘sBessie‘sbirthdayandtimeforpartygames!BessiehasinstructedtheN(1<=N<=100,000)cowsconvenientlynumbered1..Ntositinacircle(sothatcowi[exceptattheends]sitsnextto 查看详情
洛谷p2873[usaco07dec]泥水坑mudpuddles
P2873[USACO07DEC]泥水坑MudPuddles题目描述FarmerJohnisleavinghishousepromptlyat6AMforhisdailymilkingofBessie.However,thepreviouseveningsawaheavyrain,andthefieldsarequitemuddy.FJstartsatthepoint(0,0)inthecoord 查看详情
洛谷p2969[usaco09dec]音符musicnotes
P2969[USACO09DEC]音符MusicNotes题目描述FJisgoingtoteachhiscowshowtoplayasong.ThesongconsistsofN(1<=N<=50,000)notes,andthei-thnotelastsforB_i(1<=B_i<=10,000)beats(thusnosongislongerthan500,000,00 查看详情
洛谷p2926[usaco08dec]拍头pattingheads
洛谷P2926[USACO08DEC]拍头PattingHeads一种是N(sqrt(val))的做法1#include<cstdio>2#include<cmath>3#defineFor(i,j,k)for(inti=j;i<=k;i++)4usingnamespacestd;56constintN=100011,VAL=1000011,inf=2e9;7inta 查看详情
洛谷p3128[usaco15dec]最大流maxflow
P3128[USACO15DEC]最大流MaxFlow题目描述FarmerJohnhasinstalledanewsystemof N-1N−1 pipestotransportmilkbetweenthe NN stallsinhisbarn(2leqNleq50,0002≤N≤50,000),convenientlynumbe 查看详情