做网站字体规范,聊城广告设计公司,图标logo设计,腾讯企业邮箱免费注册入口比赛链接#xff1a; 文章目录A HDU 1285 一B HDU 1863 起C POJ 2387 开D POJ 1502 心E HDU 5922 图F HDU 2112 论A HDU 1285 一
拓扑排序模板题#xff0c;记录每个点的入度#xff0c;然后按照入度大小以及顺序进行输出
#includeiostream
#includequeue…比赛链接
文章目录A HDU 1285 一B HDU 1863 起C POJ 2387 开D POJ 1502 心E HDU 5922 图F HDU 2112 论A HDU 1285 一
拓扑排序模板题记录每个点的入度然后按照入度大小以及顺序进行输出
#includeiostream
#includequeue
#includecstdio
#includecstring
using namespace std;
bool map[517][517];
int in[517];
priority_queueint,vectorint,greaterint q;
void topo(int n)
{for(int i1;in;i){if(in[i]0)q.push(i);}int c1;while(!q.empty()){int vq.top();q.pop();if(c!n){coutv ;c;}elsecoutvendl;for(int i1;in;i){if(!map[v][i])continue;in[i]--;if(!in[i])q.push(i);}}
}
int main()
{int n,m,i,j;while(cinnm){int k0;memset(map,0,sizeof map);memset(in,0,sizeof in);while(m--){cinij;if(map[i][j])continue;map[i][j]1;in[j];}topo(n);}
}B HDU 1863 起
最小生成树模板题
#includebits/stdc.h
using namespace std;
int n,m;
const int maxn1e632;
struct node{int u,v,w;
}edge[maxn];
int fa[maxn];
int total0;
bool cmp(node x,node y)
{return x.wy.w;
}
int sum0;
int find(int x)
{if(fa[x]x)return x;else return find(fa[x]);
}
inline void Kruskal()
{total0;sum0;for(int i1;im;i){int ufind(edge[i].u);int vfind(edge[i].v);if(uv)continue;sumedge[i].w;fa[u]v;total;if(totaln-1)break;}}
int main()
{while(cinmn){if(m0)break;for(int i1;in;i)fa[i]i;memset(edge,0,sizeof(edge));for(int i1;im;i){cinedge[i].uedge[i].vedge[i].w;}sort(edge1,edge1m,cmp);Kruskal();if(totaln-1)coutsumendl;else cout?endl;}return 0;
}C POJ 2387 开
最短路模板从n 到 1
#includeiostream
#includecstdio
#includecstring
#includestring
#includequeue
const long long inf2147483647;
const int maxn10005;
const int maxm500005;
using namespace std;
int n,m,s,num_edge0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{ //以下是数据结构书上的标准代码不懂翻书看解释edge[num_edge].nexthead[from]; //链式存储下一条出边edge[num_edge].toto; //当前节点编号edge[num_edge].disdis; //本条边的距离head[from]num_edge; //记录下一次的出边情况
}
void spfa()
{queueint q; //spfa用队列这里用了STL的标准队列for(int i1; in; i) {dis[i]inf; //带权图初始化vis[i]0; //记录点i是否在队列中同dijkstra算法中的visited数组}q.push(s); dis[s]0; vis[s]1; //第一个顶点入队进行标记while(!q.empty()){int uq.front(); //取出队首q.pop(); vis[u]0; //出队标记for(int ihead[u]; i; iedge[i].next) //邻接表遍历不多解释了也可用vector代替{int vedge[i].to; if(dis[v]dis[u]edge[i].dis) //如果有最短路就更改{dis[v]dis[u]edge[i].dis;if(vis[v]0) //未入队则入队{vis[v]1; //标记入队q.push(v);}}}}
}
int main()
{cinmn;sn;for(int i1; im; i){int f,g,w;cinfgw; addedge(f,g,w); //建图有向图连一次边就可以了addedge(g,f,w);}spfa(); //开始跑spfacoutdis[1]endl; //否则打印最短距离return 0;
}D POJ 1502 心
也是最短路模板题只是读入方式有些奇怪
#includeiostream
#includecstdio
#includecstring
#includequeue
#includealgorithm#define inf 0x7f
using namespace std;
const int MAXN10010,MAXM500010;struct XY{int w,to,pre;
}e[MAXM];struct XX{int dis,num;
}d[MAXN],tmp;struct cmp1{bool operator ()(XX a,XX b){return a.disb.dis;}
};
char w[110];
int n,s,sz0;
int las[100010];
bool flag[MAXN];
priority_queueXX,vectorXX,cmp1 q;void init()
{sz0;memset(las,0,sizeof(las));memset(flag,0,sizeof(flag));
}
void add(int x,int y,int w){sz;e[sz].toy;e[sz].ww;e[sz].prelas[x];las[x]sz;
}void Dijkstra(){int min,u0;s1;d[s].dis0;q.push(d[s]);while (!q.empty()){uq.top().num;q.pop();if (flag[u]) continue;flag[u]true;for (int jlas[u];j;je[j].pre){int mue[j].to;if (d[mu].disd[u].dise[j].w){d[mu].disd[u].dise[j].w;q.push(d[mu]);}}}
}int zhuanhua(char s[])
{if(s[0]x)return inf;else{int sum0;for(int i0; istrlen(s); i)sumsum*10s[i]-0;return sum;}
}int main(){while(scanf(%d,n)!EOF){init();memset(e,0,sizeof(e));for (int i1;in;i){d[i].numi;d[i].dis2147483647;}for(int i2;in;i){for(int j1;ji;j){scanf(%s,w);int zzzhuanhua(w);add(i,j,zz);add(j,i,zz);}}Dijkstra();int maxx0;for (int i1;in;i)maxxmax(maxx,d[i].dis);cout maxx;while(!q.empty())q.pop(); }return 0;
}E HDU 5922 图
找规律表面是最小生成树但仔细看会发现将点1与其他点相连费用最低因为费用为两点之和而1是最小的数
#includeiostream
using namespace std;
typedef long long ll;
int main()
{int t;cint;for(int i1;it;i){ll n;cinn;printf(Case #%d: %lld\n,i,(n-1)*(n2)/2);}
}F HDU 2112 论
也是最短路不过每个站点都是具体的城市名可以用map实现名字与编号的唯一对应
#includeiostream
#includecstdio
#includecstring
#includestring
#includemap
#includequeue
const long long inf2147483647;
const int maxn30005;
const int maxm70005;
using namespace std;
int n,m,s,num_edge0;
mapstring,intmp;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{ //以下是数据结构书上的标准代码不懂翻书看解释edge[num_edge].nexthead[from]; //链式存储下一条出边edge[num_edge].toto; //当前节点编号edge[num_edge].disdis; //本条边的距离head[from]num_edge; //记录下一次的出边情况
}
void spfa()
{queueint q; //spfa用队列这里用了STL的标准队列for(int i1; in; i) {dis[i]inf; //带权图初始化vis[i]0; //记录点i是否在队列中同dijkstra算法中的visited数组}q.push(s); dis[s]0;
vis[s]1; //第一个顶点入队进行标记while(!q.empty()){int uq.front(); //取出队首q.pop(); vis[u]0; //出队标记for(int ihead[u]; i; iedge[i].next) //邻接表遍历不多解释了也可用vector代替{int vedge[i].to; if(dis[v]dis[u]edge[i].dis) //如果有最短路就更改{dis[v]dis[u]edge[i].dis;if(vis[v]0) //未入队则入队{vis[v]1; //标记入队q.push(v);}}}}
}
void init()
{num_edge0;mp.erase(mp.begin(),mp.end());memset(head,0,sizeof(head));memset(edge,0,sizeof(edge));}
int main()
{while(cinm){init();if(m-1)break;string a,end,b;cinaend;mp[a]1;s1;int cnt1;for(int i1; im; i){int w;cinabw;if(mp[a]0)mp[a]cnt;if(mp[b]0)mp[b]cnt; addedge(mp[a],mp[b],w); //建图有向图连一次边就可以了addedge(mp[b],mp[a],w);}ncnt;spfa(); //开始跑spfaif(mp[end]0||dis[mp[end]]inf)cout-1endl;else coutdis[mp[end]]endl; //否则打印最短距离}return 0;
}
