邻接矩阵表示法创建无向图
采用邻接矩阵表示法创建无向图G ，依次输出各顶点的度。
输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。
输入第二行为顶点的信息，每个顶点只能用一个字符表示。
依次输入j行，每行输入一条边依附的顶点。
依次输出各顶点的度，行末没有最后的空格。
输入样例:
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
输出样例:
2 3 3 3 3#include<stdio.h>
int flag=1;
int main(){
int a[10][10]={0},b[100],i,m,n;
char x,j,k;
scanf("%d %d\n",&n,&m);
for(i=0;i<n;i++){
scanf("%c",&x);
b[x]=i;
}
for(i=0;i<m;i++){
getchar();
scanf("%c%c",&j,&k);//加取地址符号
a[b[j]][b[k]]=a[b[k]][b[j]]=1;
}
for(i=0;i<n;i++){
int sum=0;
for(j=0;j<n;j++){
sum+=a[j][i];
}
if(flag){printf("%d",sum);flag=0;}
else printf(" %d",sum);
}
return 0;
}
邻接表创建无向图
采用邻接表创建无向图G ，依次输出各顶点的度。
输入格式
输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。
输入第二行为顶点的信息，每个顶点只能用一个字符表示。
依次输入j行，每行输入一条边依附的顶点。
输出格式:
依次输出各顶点的度，行末没有最后的空格
输入样例:
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
输出样例:
2 3 3 3 3#include<stdio.h>
int flag=1;
int main(){
int a[10][10]={0},b[100],i,m,n;
char x,j,k;
scanf("%d %d\n",&n,&m);
for(i=0;i<n;i++){
scanf("%c",&x);
b[x]=i;
}
for(i=0;i<m;i++){
getchar();
scanf("%c%c",&j,&k);//加取地址符号
a[b[j]][b[k]]=a[b[k]][b[j]]=1;
}
for(i=0;i<n;i++){
int sum=0;
for(j=0;j<n;j++){
sum+=a[j][i];
}
if(flag){printf("%d",sum);flag=0;}
else printf(" %d",sum);
}
return 0;
}列出连通集
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照”{ v1 v2 … vk }”的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }#include<bits/stdc++.h>
using namespace std;
int vi[11],g[11][11],n,e;
queue<int>q;
void dfs(int v){
int i;
printf("%d ",v);
vi[v]=1;
for(i=0;i<n;i++){
if(vi[i]==0&&g[v][i]){
dfs(i);
}
}
}
void bfs(int v){
int i;
vi[v]=1;
q.push(v);
while(!q.empty()){
for(i=0;i<n;i++){
if(vi[i]==0&&g[q.front()][i]){
vi[i]=1;
q.push(i);
}
}
printf("%d ",q.front());
q.pop();
}
}
int main(){
cin>>n>>e;
int i,v1,v2;
for(i=0;i<e;i++){
cin>>v1>>v2;
g[v1][v2]=g[v2][v1]=1;
}
for(i=0;i<n;i++){
if(vi[i]==0){
printf("{ ");
dfs(i);
printf("}\n");
}
}
memset(vi,0,sizeof(vi));
for(i=0;i<n;i++){
if(vi[i]==0){
printf("{ ");
bfs(i);
printf("}\n");
}
}
return 0;
}图深度优先遍历
编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。
输入格式:
输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。
输出格式:
输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。
输入样例1:
3 3
0 1
1 2
0 2
输出样例1:
0 1 2
输入样例2:
4 4
0 2
0 1
1 2
3 0
输出样例2:
0 1 2 3 #include<bits/stdc++.h>//＜（＾－＾）＞正确
using namespace std;
int a[20000][51],vi[20000];
int n,e;
void dfs(int v){
printf("%d ",v);
vi[v]=1;
int i;
for(i=0;i<e;i++){
if(vi[i]==0&&a[v][i])
dfs(i);
}
}
int main(){
cin>>n>>e;
int v1,v2,i;
for(i=0;i<e;i++){
cin>>v1>>v2;
a[v1][v2]=1;
}
for(i=0;i<n;i++){
if(vi[i]==0){
dfs(i);
}
}
return 0;
}单源最短路径
请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点，编号为0至n-1，以顶点0作为源点。
输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
输出格式:
输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。
输入样例:
4 4
0 1 1
0 3 1
1 3 1
2 0 1
输出样例:
1 1 #include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f
struct node{
int x;
int dis;
};
vector<node>biao[20005];
int dist[20005],vi[20005],v,n;
void dij(int v){
fill(dist,dist+20005,inf);
dist[v]=0;
for(int i=0;i<n;i++){
int minx=inf,u;
for(int j=0;j<n;j++){
if(vi[j]==0&&dist[j]<minx){
minx=dist[j];
u=j;
}
}
if(minx==inf)return ;
vi[u]=1;
for(int k=0;k<biao[u].size();k++){
int x=biao[u][k].x;
if(vi[x]==0&&dist[u]+biao[u][k].dis<dist[x]){
dist[x]=dist[u]+biao[u][k].dis;
}
}
}
}
int main(){
int e,x,y,z,i;
cin>>n>>e;
for(i=0;i<e;i++){
cin>>x>>y>>z;
node t={y,z};
biao[x].push_back(t);
}
dij(0);
for(int i=1;i<n;i++){
if(dist[i]!=inf)cout<<dist[i]<<' ';
}
return 0;
}
最短路径算法(Floyd-Warshall)
在带权有向图G中，求G中的任意一对顶点间的最短路径问题，也是十分常见的一种问题。
解决这个问题的一个方法是执行n次迪杰斯特拉算法，这样就可以求出每一对顶点间的最短路径，执行的时间复杂度为O(n3)。
而另一种算法是由弗洛伊德提出的，时间复杂度同样是O(n3)，但算法的形式简单很多。
在本题中，读入一个有向图的带权邻接矩阵（即数组表示），建立有向图并使用Floyd算法求出每一对顶点间的最短路径长度。
输入格式:
输入的第一行包含1个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。
当i和j相等的时候，保证对应的整数为0。
输出格式:
共有n行，每行有n个整数，表示源点至每一个顶点的最短路径长度。
如果不存在从源点至相应顶点的路径，输出-1。对于某个顶点到其本身的最短路径长度，输出0。
请在每个整数后输出一个空格，并请注意行尾输出换行。
输入样例:
4
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
输出样例:
0 3 2 1
6 0 4 7
2 5 0 3
3 6 1 0 #include<bits/stdc++.h>
using namespace std;
int o=100000;
int main(){
int n,m,x,i,j,k;
cin>>n;
int f[51][51];
for(i=0;i<n;i++){//重置数组（每个元素都为无穷大）
for(j=0;j<n;j++){
f[i][j]=o;
}
}
m=o;
for(i=0;i<n;i++){//对角线元素为0
f[i][i]=0;
}
for(i=0;i<n;i++){//输入初始值
for(j=0;j<n;j++){
cin>>x;
if(x!=0)f[i][j]=x;
}
}
for(k=0;k<n;k++){//弗洛伊德算法
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(f[i][j]>f[i][k]+f[k][j])
f[i][j]=f[i][k]+f[k][j];
}
}
}
for(i=0;i<n;i++){//输出
for(j=0;j<n;j++){
if(f[i][j]>=m)
printf("-1 ");
else
printf("%d ",f[i][j]);
}
cout<<endl;
}
return 0;
}哈利·波特的考试(Floyd)
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。
输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。
输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
输入样例:
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例:
4 70#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int g[101][101];
void floyd(int n){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
}
}
}
}
int minn(int x,int n){
int dis=-1;
for(int i=1;i<=n;i++){
if(i!=x&&g[x][i]==inf)return inf;//如果x点与i点距离无限长就return无穷大
else dis=max(dis,g[x][i]);//dis是x与i距离较大的点
}
return dis;//返回i点与所有点距离最大的长度
}
int main(){
int m,n,i,j,x,y,z;
cin>>n>>m;
for(i=1;i<=n;i++){//重置
for(j=1;j<=n;j++){
g[i][j]=inf;
}
g[i][i]=0;//对角线=0
}
for(i=0;i<m;i++){//输入
cin>>x>>y>>z;
g[x][y]=g[y][x]=z;
}
floyd(n);//弗洛伊德算法
int mindis=inf,in=1,dis;
for(i=1;i<=n;i++){//从小到大遍历每种动物
//返回i点与所有点距离最大的长度，再从所有点返回的最大距离中找出最小的一个
dis=minn(i,n);
if(dis<mindis){
mindis=dis;//再从所有点返回的最大距离中找出最小的一个
in=i;//记录动物编号
}
}//如果有一个点与其他点是孤立的，那么所有点的返回值dis都为无穷大
if(mindis==inf)printf("0");
else printf("%d %d",in,mindis);
return 0;
}旅游规划 (Floyd)
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例:
3 40#include<bits/stdc++.h>
using namespace std;
int fee[501][501];//计算最低费用
int g[501][501];//用于计算两点之间的最短距离
#define o 0x3f3f3f;//3个3f!
int main(){
int n,m,s,d,i,j,k;
int c1,c2,l,f;
cin>>n>>m>>s>>d;
for(i=0;i<n;i++){//重置
for(j=0;j<n;j++){
g[i][j]=o;
}g[i][i]=0;
}
for(i=0;i<m;i++){//输入
cin>>c1>>c2>>l>>f;
g[c1][c2]=l;
g[c2][c1]=l;
fee[c1][c2]=f;
fee[c2][c1]=f;
}
for(k=0;k<n;k++){//Floyd算法
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(g[i][j]>g[i][k]+g[k][j]){
g[i][j]=g[i][k]+g[k][j];
fee[i][j]=fee[i][k]+fee[k][j];
}
else if(g[i][j]==g[i][k]+g[k][j]){
fee[i][j]=min(fee[i][j],fee[i][k]+fee[k][j]);
}
}
}
}
cout<<g[s][d]<<' '<<fee[s][d];
return 0;
}最短路径 (Floyd)
给定一个有N个顶点和E条边的无向图，顶点从0到N−1编号。请判断给定的两个顶点之间是否有路径存在。如果存在，给出最短路径长度。
这里定义顶点到自身的最短路径长度为0。
进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。
随后E行，每行给出一条边的两个顶点。每行中的数字之间用1空格分隔。
最后一行给出两个顶点编号i，j（0≤i,j<N）,i和j之间用空格分隔。
输出格式:
如果i和j之间存在路径，则输出”The length of the shortest path between i and j is X.”，X为最短路径长度，
否则输出”There is no path between i and j.”。
输入样例1:
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 3
输出样例1:
The length of the shortest path between 0 and 3 is 2.
输入样例2:
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 6
输出样例2:
There is no path between 0 and 6.#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f
int n;
int g[11][11];
void floyed(){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
}
int main(){
int m,i,j,x,y;
cin>>n>>m;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
g[i][j]=inf;
}
g[i][i]=0;
}
for(i=0;i<m;i++){
cin>>x>>y;
g[x][y]=1;g[y][x]=1;
}
floyed();
cin>>x>>y;
if(g[x][y]!=inf)cout<<"The length of the shortest path between "<<x <<" and "<<y<<" is "<<g[x][y]<<'.';
else cout<<"There is no path between "<<x<<" and "<<y<<'.';
return 0;
}哥尼斯堡的“七桥问题”
哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。
这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？
输入格式:
输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。
输出格式:
若欧拉回路存在则输出1，否则输出0。
输入样例1:
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6
输出样例1:
1
输入样例2:
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4
输出样例2:
0代码
#include<bits/stdc++.h>
using namespace std;
int f[1001];
int fu(int x){
if(f[x]==x)return x;
return f[x]=fu(f[x]);
}
int main(){
int m,n,i,j,x,y,in[1001];
cin>>n>>m;
for(i=1;i<=n;i++){//重置
f[i]=i;
in[i]=0;
}
for(i=0;i<m;i++){
cin>>x>>y;
int a=fu(x);//寻找a,b的祖先
int b=fu(y);
if(a!=b)f[a]=b;
in[x]++;x,y
in[y]++;
}
int c1=0,c2=0;
for(i=1;i<=n;i++){
if(f[i]==i)c2++;//看看有几个连通图
}
for(i=1;i<=n;i++){
if(in[i]%2==0)c1++;//每个节点走过偶数次
}
if(c1==n&&c2==1)printf("1\n");
else printf("0\n");
return 0;
}公路村村通
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
128
#include<bits/stdc++.h>
using namespace std;
struct node{
int a,b,cost;
}e[3001];
int f[1001],n,m;
int fu(int x){
if(f[x]==x)return x;
return f[x]=fu(f[x]);
}
int mer(int x,int y){
int a=fu(x);int b=fu(y);
if(a!=b){f[a]=b;return 1;}
return 0;
}
int cmp(node a,node b){
return a.cost<b.cost;
}
int main(){
cin>>n>>m;
int x,y,z;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=0;i<m;i++){
cin>>x>>y>>z;
e[i].cost=z;e[i].a=x;e[i].b=y;
}
sort(e,e+m,cmp);
int sum=0;
for(int i=0;i<m&&n>1;i++){
if(mer(e[i].a,e[i].b)==1){
sum+=e[i].cost;
n--;
}
}
if(n==1){
cout<<sum;
}
else cout<<"-1";
return 0;
}最短工期
一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。
输入格式：
首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。
输出格式：
如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出”Impossible”。
输入样例 1：
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
输出样例 1：
18
输入样例 2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5
输出样例 2：
Impossible#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int to;
int cost;
}Node;
int in[101],dis[101],cnt=0;
stack<int>Q;//存的是可以开始的工程（即没有子任务）
vector<Node>T[101]; //存的是一个任务及它的下一任务（不止一个）
void ToPo(){
while(!Q.empty()){
int t=Q.top();
Q.pop();
cnt++;//用来计算每个任务是否都被遍历
for(int i=0;i<T[t].size();i++){
int to=T[t][i].to;//因为任务t的下一任务不止一个所以加[i]
int cost=T[t][i].cost;
in[to]--;//把这个点以及连接它子任务的一个边（入度）抽掉
if(in[to]==0)Q.push(to);//当in[]为零的时候表示入度为零，即这个任务的子任务已全部被完成
dis[to]=max(dis[to],dis[t]+cost);//不断更新时间， 要取最大的时间值。
}
}
}
int main(){
int N,M;
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
Node t;
t.to=b;t.cost=c;
T[a].push_back(t);
in[b]++;//加的是b点的入度
}
for(int i=0;i<N;i++)
if(in[i]==0) Q.push(i);//找没有入度的点
ToPo();
int maxx=0;
for(int i=0;i<N;i++)
maxx=max(maxx,dis[i]);
if(cnt==N)printf("%d\n",maxx);//每个任务是否都被遍历
else printf("Impossible\n");
}最短工期
一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。
输入格式：
首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。
输出格式：
如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出”Impossible”。
输入样例 1：
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
输出样例 1：
18
输入样例 2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5
输出样例 2：
Impossible#include<bits/stdc++.h>
using namespace std;
struct node{
int to;
int cost;
};
int in[101],dis[101],cnt=0;
stack<int>Q;//存的是可以开始的工程（即没有子任务）
vector<node>T[101]; //存的是一个任务及它的下一任务（不止一个）
void ToPo(){
while(!Q.empty()){
int t=Q.top();
Q.pop();
cnt++;//用来计算每个任务是否都被遍历
for(int i=0;i<T[t].size();i++){
int to=T[t][i].to;//因为任务t的下一任务不止一个所以加[i]
int cost=T[t][i].cost;
in[to]--;//把这个点以及连接它子任务的一个边（入度）抽掉
if(in[to]==0)Q.push(to);//当in[]为零的时候表示入度为零，即这个任务的子任务已全部被完成
dis[to]=max(dis[to],dis[t]+cost);//不断更新时间， 要取最大的时间值。
}
}
}
int main(){
int N,M;
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
node t={b,c};
T[a].push_back(t);
in[b]++;//加的是b点的入度
}
for(int i=0;i<N;i++)
if(in[i]==0) Q.push(i);//找没有入度的点
ToPo();
int maxx=0;
for(int i=0;i<N;i++)
maxx=max(maxx,dis[i]);
if(cnt==N)printf("%d\n",maxx);//每个任务是否都被遍历
else printf("Impossible\n");
}任务调度的合理性
假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。
但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。
输入格式:
输入说明：输入第一行给出子任务数N（≤100），子任务按1~N编号。随后N行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数K，随后给出K个子任务编号，整数之间都用空格分隔。
输出格式:
如果方案可行，则输出1，否则输出0。
输入样例1:
12
0
0
2 1 2
0
1 4
1 5
2 3 6
1 3
2 7 8
1 7
1 10
1 7
输出样例1:
1
输入样例2:
5
1 4
2 1 4
2 2 5
1 3
0
输出样例2:
0#include<bits/stdc++.h>
using namespace std;
vector<int>q[101];
stack<int>s;
int cnt=0,i,j,n,in[101];
void creat(){
while(!s.empty()){
int t=s.top();
cnt++;
s.pop();
for(i=0;i<q[t].size();i++){
int x=q[t][i];
in[x]--;
if(in[x]==0)s.push(x);
}
}
if(cnt==n)cout<<'1';
else cout<<'0';
}
int main()
{
int sum,num;
cin>>n;
for(i=1;i<=n;i++){
cin>>sum;
for(j=1;j<=sum;j++){
cin>>num;
q[num].push_back(i);
in[i]++;
}
}
for(i=1;i<=n;i++){
if(in[i]==0)s.push(i);
}
creat();
return 0;
}以上作为笔记使用
文章出处登录后可见！
