1. 求一个有向图所有顶点入度的和
输入有向图的顶点个数，边数以及各顶点之间的关联情况，要求求出这个有向图的所有顶点入度的总和。
【输入格式】
第1行：2个空格分开的整数n(2<=n<=200)和m(10<=m<=20000),分别表示图的顶点和边数。
第2至m+1行：每行2个空格分开的整数i,j,i表示一条边的起点，j表示终点。
【输出格式】
只有1行，为1个整数，表示所有顶点的入度总和。
【样例输入】
3 6
1 2
1 3
2 1
2 3
3 1
3 2
【样例输出】
6
#include <iostream>
using namespace std;
int a[][],n,m,ans = ;
void init()
{
int i,j,k;
cin >> n >> m;
for(i=;i<=m;i++)
{
cin >> j >> k;
a[j][k] = ;
}
}
int main()
{
init();
for(int i = ;i <= n; i++){
for(int j = ;j <= n;j++){
if(a[j][i] == ){
ans++;
} }
}
cout << ans << endl;
}
2、同班同学
有一个学校拥有N位学生，有些学生彼此是同班同学。我们根据“我的同班同学的同班同学也是我的同班同学”；也就是，如果A和B是同班同学，而且B和C是同班同学，那么A和C也是同班同学；换言之，A、B、C都是同一班的学生。当输入所有学生之间的这种关系后，计算全校共有几个班级？
【输入格式】
第1行，输入N和M，N为学生个数，M为有同班关系的同学的对数，（0<=N<=1000，0<=M<=100）接下来M行，输入有同班关系的学生编号。
【输出格式】
共1行，全校班级的个数
【样例输入】
6 5
1 2
3 4
4 5
4 6
5 6
【样例输出】
2
#include<iostream>
using namespace std;
int g[][],visited[];
int sum = ,n,m;
int total = ;
void dfs(int cur){
visited[cur] = ;
sum++;
if(sum==n)
return;
for(int i=;i<=n;i++){
if(g[cur][i]==&&visited[i]!=){
visited[i]=;
dfs(i);
}
}
}
int main(){
cin>>n>>m;
int i,j,a,b;
for(i=;i<=m;i++){
cin>>a>>b;
g[a][b]=;
g[b][a]=;
}
for(i = ;i <= n;i++){
if(visited[i] != ){
dfs(i);
total += ;
}
}
cout << total << endl;
return ;
}
1、铲雪车
随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？
【输入格式】
输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。
第2行表示街道的数量n（n<100），接下来n行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20 km/h，不铲雪时前进速度为50 km/h。
保证：铲雪车从起点一定可以到达任何街道。
【输出格式】
铲掉所有街道上的雪并且返回出发点的最短时间，精确到分钟。
【样例输入】
0 0
3
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000
【样例输出】
3:55
【注释】
3小时55分钟
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
double fun(int a,int b,int c,int d)
{
double x,y;
x = abs(a - c);
y = abs(b - d);
return sqrt(x * x + y * y) / ;
}
int main(){
int x, y;
while(cin >> x >> y)
{
int n, x1, y1, x2, y2;
double sum = ;
cin >> n;
for(int i = ; i <= n; i ++)
{
cin >> x1 >> y1 >> x2 >> y2;
sum += fun(x1,y1,x2,y2);
}
int T = sum - ;
double t = sum - T;
int te = floor(t * + 0.5);
if(te >= )
{
T ++;
te -= ;
}
cout << T << ":";
if(te < ) cout << "";
cout << te << endl;
}
return ;
}
2．骑马修栅栏
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
John是一个懒惰的人，他讨厌骑马，因此从来不两次经过同一个栅栏。现在你编写一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每一个栅栏恰好都经过一次。John能从任何一个顶点（即两个栅栏的交点）开始骑马，在任意一个顶点结束。
每个栅栏连接两个顶点，顶点用1到500标号（虽然有的农场并没有500个顶点）。一个顶点上可连接任意多（>=1）个栅栏。所有栅栏都是连通的（也就是你可以从任意一个栅栏到达另外的所有栅栏）。
你的程序必须输出骑马的路径（用路上依次经过的顶点号码表示）。我们如果把输出的路径看成一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个（也就是输出第一个较小的数，如果还有多组解，输出第二个较小的数，等等）。输出数据保证至少有一个解。
【输入格式】
第1行：一个整数F（1<=F<=1024）,表示栅栏的数目。
第2到F+1行：每行两个整数i，j（1<=i , j<=500）表示这条栅栏连接i与j号顶点。
【输出格式】
输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解释正确的。
【样例输入】
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
【样例输出】
1
2
3
4
2
5
4
6
5
7
#include <iostream>
#include <cstring> using namespace std;
int g[][];
int du[];
int circuit[];
int n,m,tot,x,y,start;
void find(int i){
for(int j = ;j <= n;j++)
if(g[i][j]){
g[i][j]--;
g[j][i]--;
find(j);
}
circuit[++tot] = i;
}
int main(){
memset(g,,sizeof(g));
cin >> m;
for(int i = ;i <= m;i++){
cin >> x >> y;
g[x][y]++;
g[y][x]++;
du[x]++;
du[y]++;
n = max(n,max(x,y));
}
start = ;
for(int i =;i <= n;i++)
if(du[i] % ){
start = i;
break;
}
tot = ;
find(start);
for(int i = tot;i >= ;i--)
cout << circuit[i] << endl;
return ;
}