程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj 2676 Network Wars(最小割，01分數規劃)

zoj 2676 Network Wars(最小割，01分數規劃)

編輯：C++入門知識

大致題意：給出一個帶權無向圖，每條邊有一個邊權wi,求將S和T分開的一個割邊集C，使得該割邊集的平均邊權最小，即最小化∑wi / |C| 。

詳見amber關於最小割模型的論文

思路：amber論文中詳細講解了如何轉化成函數及建圖，值得注意的是當邊被重新賦權後,對於wi < 0 的邊權，該邊必然在最小割中，不必再建邊，直接加入最大流中即可，因為求最小割時邊權都為正值。

最後輸出的是所選割邊的序號。求割邊無非是從源點dfs,每次走殘量網絡中流量大於0的邊並標記端點，最後判斷邊的兩個端點一個標記一個未標記，那麼該邊便是割邊。

這題我TLE了13次，最後是因為Dinic的原因，可能之前的那個模板耗時太長了。改成了學長的Dinic,瞬間就A了。

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-7

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 210;
const int maxm = 6000;
int s,t;
struct node
{
    int u,v;
    double w;
    int next;
    int re;
}p[maxm],edge[maxm];
int n,m;
int cnt,head[maxn];
int dist[maxn],vis[maxn];

void init()
{
    cnt = 0;
    memset(head,-1,sizeof(head));
}

void add(int u, int v, double w)
{
    edge[cnt] = (struct node){u,v,w,head[u],cnt+1};
    head[u] = cnt++;

    edge[cnt] = (struct node){v,u,0,head[v],cnt-1};
    head[v] = cnt++;
}

bool bfs()
{
    queue  que;
    memset(dist, 0, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    while(!que.empty()) que.pop();
    vis[s] = 1;
    que.push(s);
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if(edge[i].w && !vis[v])
            {
                que.push(v);
                vis[v] = 1;
                dist[v] = dist[u]+1;
            }
        }
    }
    if(dist[t] == 0)
		return false;
	return true;
}

double dfs(int u, double delta)
{
    if(u == t) return delta;
    double ret = 0,tmp;

	for(int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].v;
		if(edge[i].w && dist[edge[i].v] == dist[u]+1 && (tmp = dfs(v,min(delta,edge[i].w))))
		{
			edge[i].w -= tmp;
			edge[edge[i].re].w += tmp;
			return tmp;
		}
	}
	if(!ret) dist[u] = -1;
	return ret;

}

double Dinic()
{
    double ret = 0,res;
    while(bfs())
    {
       while(res = dfs(s,INF))
			ret += res;
    }
    return ret;
}

bool ok(double mid)
{
    init();
    double flow = 0;

    for(int i = 1; i <= m; i++)
    {
        if(p[i].w > mid)
        {
            add(p[i].u,p[i].v,p[i].w-mid);
            add(p[i].v,p[i].u,p[i].w-mid);
        }
        else
            flow += p[i].w - mid;
    }

    flow += Dinic();
    if(flow > eps)
        return true;
    else return false;
}

void dfs_cut(int u)
{
    vis[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(!vis[v] && edge[i].w > 0)
        {
            dfs_cut(v);
        }
    }
}

int main()
{
    int item = 0;
    while(~scanf(%d %d,&n,&m))
    {
    	s = 1;
    	t = n;
        item += 1;
        if(item >= 2)
            printf(
);
        double low = INF,high = 0,mid;

        for(int i = 1; i <= m; i++)
        {
            scanf(%d %d %lf,&p[i].u, &p[i].v, &p[i].w);
            low = min(low,p[i].w);
            high = max(high,p[i].w);
        }

        while( fabs(high - low) > eps)
        {
            mid = (high + low)/2.0;
            if( ok(mid) )
                low = mid;
            else high = mid;
        }

        memset(vis,0,sizeof(vis));
        dfs_cut(1);
        int count = 0;
        int ans[maxm];
        for(int i = 1; i <= m; i++)
        {
            if(vis[p[i].u] + vis[p[i].v] == 1 || p[i].w <= mid)
                ans[++count] = i;
        }

        printf(%d
,count);
        for(int i = 1; i <= count-1; i++)
            printf(%d ,ans[i]);
        printf(%d
,ans[count]);
    }
    return 0;
}