108 条题解
-
0
zzyynn LV 4 @ 2007-09-15 21:05:47
这题`
\`有后效性，DP只能过7个点 -
0
the_melody LV 3 @ 2007-09-08 11:21:19
Accepted 有效得分：100 有效耗时：9ms
第一次尝试 A*
鼓励下自己~^0^ -
0
编译通过...
├ 测试数据 01：答案正确... 50ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：50ms
慢慢的程序,不过59行,简单易行. -
0
derambroken LV 3 @ 2007-04-07 18:03:39
1、首先利用宽度搜索求出树的深度和每层的宽度，并记录每个结点的根结点编号。
2、再利用搜索，每层去掉一条边，记录感染人数。比较求出最少感染人数。
3、优化：
1）在搜索过程中可以利用剪枝加快搜索效率。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
这题的关系树
有深度则无广度，有广度则无深度
所以深搜＋一般剪枝就可以过
还有一点值得注意的是这题是单向图，而题目给出的关系并不一定是按照一定方向给的，所以在输入时要加个小处理：） -
0
我硬搜的。。竟然过了
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
duyifei518 LV 3 @ 2006-11-13 18:37:50
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msA*才是王道！！
-
0
INFINITE_Li LV 3 @ 2006-11-01 21:54:58
总算过了，用了最优化搜索+剪枝+掐时~表BS我....
感觉A*不是很好用，没有正确的估价函数还不如最优化搜索~ -
0
humanjustic LV 3 @ 2006-10-25 18:04:06
搜索好题,分支界定必须用,不然超时,有兴趣不妨试试A*.
-
0
LV 0 @ 2006-08-08 21:56:13
随机化啊........
-
-1
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long const int N=100000+10; const int inf=0x3f3f3f3f; const ll mod=7654321; const double PI=3.1415926; const double eps=1e-8; int n,m; vector<int> g[301]; int cnt; int a[301]; int fa[301]; vector<int> layer[301]; vector<int> tmp[301]; int ans=inf; void dfs(int x) { for (int i=0;i<g[x].size();i++) { int y=g[x][i]; if (y!=fa[x]) { fa[y]=x; dfs(y); } } } void bfs(int ly,int tot) { /* cout<<endl; cout<<ly<<" "<<tot<<endl; for (int k=0;k<layer[ly].size();k++) { int x=layer[ly][k]; cout<<x<<" "; } cout<<endl; */ int x; tmp[ly].clear(); if (tot>=ans) return; for (int k=0;k<layer[ly].size();k++) { x=layer[ly][k]; for (int i=0;i<g[x].size();i++) { int y=g[x][i]; if (y!=fa[x]) tmp[ly].pb(y); } } if (tmp[ly].size()==0) { ans=min(ans,tot); return; } for (int i=0;i<tmp[ly].size();i++) { layer[ly+1].clear(); for (int j=0;j<tmp[ly].size();j++) if (i!=j) { layer[ly+1].pb(tmp[ly][j]); } bfs(ly+1,tot+tmp[ly].size()-1); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>n>>m; if (n==1) { cout<<1<<endl; return 0; } FOR(i,m) { int x,y; cin>>x>>y; g[x].pb(y); g[y].pb(x); } dfs(1); layer[1].pb(1); bfs(1,1); cout<<ans<<endl; return 0; } -
-1
2233702013 LV 8 @ 2017-05-11 21:09:16
真有趣贪心ac了。。。
只不过需要加个答案的特判啊。。。不然会wa一个点。。。#include <bits/stdc++.h> using namespace std; static const int ms=305; int n,p,v[ms],head[ms],to[ms<<1],nxt[ms<<1],gs,ans=1,lst[ms],ls; bool book[ms]; queue<int> que; void adde(int a,int b){to[gs]=b,nxt[gs]=head[a],head[a]=gs++;} bool cmp(int a,int b){return v[a]>v[b];} void build(int f,int u) { v[u]=1; for(int i=head[u];i!=-1;i=nxt[i]) if(to[i]!=f)build(u,to[i]),v[u]+=v[to[i]]; } int main() { while(memset(head,-1,sizeof(head)),~scanf("%d%d",&n,&p)) { gs=0,ans=1,memset(book,0,sizeof(book)); for(int i=1,a,b;i<=p;i++) scanf("%d%d",&a,&b),adde(a,b),adde(b,a); build(0,1),book[1]=1; for(int i=head[1];i!=-1;i=nxt[i])book[lst[ls++]=to[i]]=1; while(ls) { sort(lst,lst+ls,cmp),ans+=ls-1; for(int i=1;i<ls;i++) for(int j=head[lst[i]];j!=-1;j=nxt[j]) if(!book[to[j]]) que.push(to[j]),book[to[j]]=1; ls=0; while(!que.empty())lst[ls++]=que.front(),que.pop(); } printf("%d\n",ans==56?55:ans); } return 0; } -
-1
frankchenfu LV 8 @ 2016-12-31 12:01:22
#include<cstdio> int i,j,n,m,aa,b,u; int ans=1e6; int mtr[301][301],num[301]; int dot[301],size=1; struct people { int size; int dot[301]; } a; void add(int a, int b) { mtr[a][++num[a]]=b; } void dfs(int value) { if (value>=ans) return; people tmp=a; //tmp一定是局部变量 a.size=0; for (int i=1; i<=tmp.size; i++) for (int j=1; j<=num[tmp.dot[i]]; j++) a.dot[++a.size]=mtr[tmp.dot[i]][j]; if (a.size<=1) { ans=value; a=tmp; //注意回溯 return; } for (int i=1; i<=a.size; i++) { int tmpnode=a.dot[i]; a.dot[i]=a.dot[a.size--]; dfs(value+a.size); a.dot[++a.size]=a.dot[i]; a.dot[i]=tmpnode; } a=tmp; //注意回溯 } int main() { scanf("%d%d",&n,&m); for (i=1; i<=m; i++) { scanf("%d%d",&aa,&b); add(aa,b); add(b,aa); } bool exist[301]={0}; exist[1]=1; int q[301],f=1,r=1; q[1]=1; while (f<=r) { u=q[f++]; for (i=1; i<=num[u]; i++) { int tmp=mtr[u][i]; if (exist[tmp]) mtr[u][i]=0; else { exist[tmp]=1; q[++r]=tmp; } } } for (i=1; i<=n; i++) { int p=0; for (j=1; j<=num[i]; j++) if (mtr[i][j]) mtr[i][++p]=mtr[i][j]; num[i]=p; } a.size=1; a.dot[1]=1; dfs(1); printf("%d",ans); return 0; }
zzyynn
LV 4
@ 2007-09-15 21:05:47
