题意：N个点，M条边，在一个点放一个灯可以照亮与这个点相邻的边。问照亮所有的路最少需要多少个灯，如果最小值有多种情况，取边同时被两个灯照亮的情况。(N <= 1000, M < N)。
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1800
——>>设灯数为x，只被一个灯照亮的边数为b，则要使 y = kx + b 最小。
设d[i][j]为第i个灯在其父结点f在状态为j的情况下的y值。
第i个点要么放灯，要么不放，取放与不放的最小值。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn = 1000 + 10;
const int K = 2000;
int d[maxn][2];
bool vis[maxn][2];
vector<int> G[maxn];int dp(int i, int j, int f)
{if(vis[i][j]) return d[i][j];vis[i][j] = 1;int& ans = d[i][j];ans = K; //第i个点放灯int cnt = G[i].size();for(int u = 0; u < cnt; u++){int v = G[i][u];if(v != f){ans += dp(v, 1, i);}}if(f != -1 && !j) ans++;if(f == -1 || j) //第i个点不放灯{int sum = 0;for(int u = 0; u < cnt; u++){int v = G[i][u];if(v != f){sum += dp(v, 0, i);}}if(f != -1) sum++;ans = min(ans, sum);}return ans;
}int main()
{int T, N, M, i, u, v;scanf("%d", &T);while(T--){scanf("%d%d", &N, &M);for(i = 0; i < N; i++) G[i].clear();for(i = 0; i < M; i++) //建图{scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}memset(vis, 0, sizeof(vis));int ret = 0;for(i = 0; i < N; i++)if(!vis[i][0]) ret += dp(i, 0, -1);printf("%d %d %d\n", ret/K, M-ret%K, ret%K);}return 0;
}