[BZOJ 1051]受欢迎的牛
Tarjan缩点第一题……
很容易想到找出度为0的点(当且仅当这样的点有一个时有解),但是在有环图上这个方法会失效。
处理方法是,用Tarjan的强联通分量算法求出所有SCC,然后把每个SCC缩成一个点,然后再在缩点之后的图上求解即可(这个图是DAG。原因很简单,要是有环还能接着缩)。
代码:
/************************************************************** Problem: 1051 User: danihao123 Language: C++ Result: Accepted Time:72 ms Memory:1692 kb ****************************************************************/ #include <cstdio> #include <stack> #include <algorithm> using namespace std; const int maxn=10005,maxm=50005; int first[maxn]; int next[maxm],to[maxm]; int graph_cnt=0; inline void AddEdge(int u,int v){ graph_cnt++; next[graph_cnt]=first[u]; first[u]=graph_cnt; to[graph_cnt]=v; } int pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn]; stack<int> S; int dfs_clk=0,scc_cnt=0; void dfs(int x){ dfs_clk++; pre[x]=low[x]=dfs_clk; S.push(x); int i,u; for(i=first[x];i;i=next[i]){ u=to[i]; if(!pre[u]){ dfs(u); low[x]=min(low[x],low[u]); }else{ if(!sccno[u]) low[x]=min(low[x],pre[u]); } } if(low[x]==pre[x]){ scc_cnt++; sccsiz[scc_cnt]=0; while(true){ u=S.top(); S.pop(); sccno[u]=scc_cnt; sccsiz[scc_cnt]++; if(u==x) break; } } } int n; inline void Tarjan(){ register int i; for(i=1;i<=n;i++) if(!pre[i]) dfs(i); } bool Out[maxn]; int main(){ int m,u,v; register int i,j,ans=0; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d%d",&u,&v); AddEdge(u,v); } Tarjan(); for(i=1;i<=n;i++){ for(j=first[i];j;j=next[j]){ u=to[j]; if(sccno[i]!=sccno[u]) Out[sccno[i]]=true; } } for(i=1;i<=scc_cnt;i++){ if(!Out[i]){ if(ans){ ans=0; break; } ans=sccsiz[i]; } } if(n==1) ans=0; printf("%d\n",ans); return 0; }
[BZOJ 2429]聪明的猴子
图论填坑中……
这题不难,直接造图搞MST(严格讲是最小瓶颈生成树)即可。比较感人的是,Kruskal竟然也能过……
代码:
/************************************************************** Problem: 2429 User: danihao123 Language: C++ Result: Accepted Time:320 ms Memory:12592 kb ****************************************************************/ #include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int maxn=1001,maxm=501; int n; struct Edge{ int u,v,d; bool operator < (const Edge& x) const{ return d<x.d; } }; // DJoinst Set int p[maxn],rank[maxn]; int find_set(int x){ if(p[x]==x) return x; else return p[x]=find_set(p[x]); } void link_set(int x,int y){ if(rank[x]>rank[y]){ p[y]=x; }else{ p[x]=y; if(rank[x]==rank[y]) rank[y]++; } } inline void union_set(int x,int y){ link_set(find_set(x),find_set(y)); } inline bool is_same(int x,int y){ return find_set(x)==find_set(y); } inline void init_set(){ for(register int i=1;i<=n;i++) p[i]=i; // memset(rank,0,sizeof(rank)); } // Kruskal int m=0; Edge E[maxn*maxn]; int MST(){ register int i,ans,count=0; init_set(); sort(E,E+m); for(i=0;i<m && count<=(n-1);i++){ if(!is_same(E[i].u,E[i].v)){ union_set(E[i].u,E[i].v); ans=E[i].d; count++; } } return ans; } int MK[maxm],Tree[maxn][2]; int main(){ int monkey; register int i,j,sd,ans=0; scanf("%d",&monkey); for(i=1;i<=monkey;i++) scanf("%d",&MK[i]); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&Tree[i][0],&Tree[i][1]); for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ E[m].u=i; E[m].v=j; E[m].d=hypot(abs(Tree[i][0]-Tree[j][0]),abs(Tree[i][1]-Tree[j][1])); m++; } } sd=MST(); for(i=1;i<=monkey;i++) if(MK[i]>=sd) ans++; printf("%d\n",ans); return 0; }
[BZOJ 4034]T2
这个题名字也真是……
思路和我以前提到过的NOI2015 D1T2的做法是相似的,不过这题貌似int会爆精度……我这SB开始没发现,后来改了还慢慢出错……然后慢慢改……终于AC了……
我本来以为这个YY思路只有我和诸位读者知道,结果发现是貌似是ydc发明的……比我早的高明的不知哪里去了……
代码:
[BZOJ 1053]反素数
终于A了……
此题坑点多~
据说只需要预处理12个素数,然而我预处理了4648个……so sad
然后DFS就可以了
我无力吐槽了……我就是智商感人啊
代码: