多數題解是錯的，因為hdu上的這道題的數據比較水才可以過，可以試試discuss里給的數據，下面這幾個題解比較靠譜。

    http://blog.csdn.net/nash142857/article/details/8253913

    http://www.cnblogs.com/crisxyj/archive/2013/03/10/2952396.html

    http://hi.baidu.com/novosbirsk/item/bfcf0cd201edfc2d39f6f709

    兩份代碼的思想是完全一樣的，只是“baidu blog”那份用w[i][e]來判斷i的最短路樹是否包括邊e，而cnblog的那份是用used[x][u][v]來判斷邊u-->v是否xxx.

#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <deque>
using namespace std;
#define     MAXN    101
#define     INF     99999999
#define     debug   printf("!\n")
struct Edge { int u,v; } edge[3001];
vector<int> vertex[MAXN];
int visit[MAXN], sum[MAXN], cnt[MAXN][MAXN];        //cnt[u][v]表u--v的邊有多少條，用來處理重邊
bool used[MAXN][MAXN][MAXN];                        //used[x][u][v]x的最短路樹是否用到了邊u--v
int n, m;

void init();
void dijkstra(int s, int when, int flag);
int main()
{
    int when = 0;
    int u, v;
    while(scanf("%d%d", &n, &m) != EOF) {
        init();
        for(int i = 0; i < m; i++) {
            scanf("%d%d", &u, &v);
            vertex[u].push_back(v);
            vertex[v].push_back(u);
            edge[i].u = u, edge[i].v = v;
            cnt[u][v]++, cnt[v][u]++;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            dijkstra(i, ++when, 1);
            ans += sum[i];
        }
        for(int i = 0; i < m; i++) {
            int tmp = ans;
            int u = edge[i].u, v = edge[i].v;
            //forbid_u = edge[i].u, forbid_v = edge[i].v;       因為有重邊所以不能用這種方法
            for(int j = 1; j <= n; j++) if(used[j][u][v] && cnt[u][v] == 1) {       //不加cnt[u][v] == 1會超時。。卡的就是重邊，靠！
                int tmp = sum[j];
                sum[j] = 0;
                //vector<int> :: iterator it1 = find(vertex[u].begin(), vertex[u].end(), v);
                //vector<int> :: iterator it2 = find(vertex[v].begin(), vertex[v].end(), u);
                //*it1 = u, *it2 = v;
                cnt[u][v]--, cnt[v][u]--;
                dijkstra(j, ++when, 2);
                cnt[u][v]++, cnt[v][u]++;
                //*it1 = v, *it2 = u;     //本來是用erase的，超時了。 現在換這種方法也超時了，估計find耗時太久。
                ans = ans - tmp + sum[j];   //用新的sum[j]來代替舊的tmp
                sum[j] = tmp;
                int k ;
                for(k = 1; k <= n; k++) if(visit[k] != when) break;     //如果刪邊了以后j不能到達k(即k沒有進過隊)
                if(k <= n) {
                    ans = INF;
                    break;
                }
            }
            ans == INF ? printf("INF\n") : printf("%d\n", ans);
            ans = tmp;  //不要把這個tmp和for_j里的tmp混了..
        }
        for(int i = 0; i < m; i++) cnt[edge[i].u][edge[i].v] = cnt[edge[i].v][edge[i].u] = 0;   //初始化因為感覺memset(cnt)會不會花更多時間
    }
    return 0;
}
void dijkstra(int s, int when, int flag)
{
    int floors = 1;
    int cur = 0;
    deque<int> Q[2];
    Q[cur].push_back(s);
    visit[s] = when;
    do {
        while(!Q[cur].empty()) {
            int u = Q[cur].front();
            Q[cur].pop_front();
            for(int Size = vertex[u].size(), i = 0; i < Size; i++) {
                int v = vertex[u][i];
                if(visit[v] != when && cnt[u][v] > 0) {
                    if(flag == 1) used[s][u][v] = used[s][v][u] = true;   //第一次最短路才標記used因為懶得寫兩遍，所以要flag來標記是刪邊前還收刪邊后做的最短路，1則是預處理時的最短路，此時要標記used；2則是刪邊后的最短路，這個時候不能標記used.
                    visit[v] = when;
                    sum[s] += floors;
                    Q[1-cur].push_back(v);
                }
            }
        }
        floors++; 
        cur = 1 - cur;
    } while(!Q[cur].empty());
}
void init()
{
    memset(sum, 0, sizeof(sum));
    memset(used, false, sizeof(used));
    for(int i = 1; i <= n; i++) vertex[i].clear();
}