下面是dinic的TLE代码，然后是EK的AC代码：
#include <cstdio>
#include <cstring>

const int N = 210;
const int M = 1010;
const int INF = 0x1fffffff;

struct node
{
    int u, v, c;
}e[M*2];

int s, t, n, m, tot, din[N], dout[N], que[N], h[N], level[N], nxt[M*2];
bool visit[N];

int min(int x, int y)
{
    return  x < y ? x : y;
}

void add(int u, int v, int c)
{
    e[tot].u = u;
    e[tot].v = v;
    e[tot].c = c;
    nxt[tot] = h[u];
    h[u] = tot++;
}

bool bfs(int s, int t)
{
    int u, v, head, tail, p;
    head = tail = 0;
    que[0] = s;
    memset(level, 0, sizeof(level));
	memset(visit, false, sizeof(visit));
    level[s] = 0;
	visit[s] = true;
    while(head <= tail)
    {
        u = que[head++];
        p = h[u];
        while(p != -1)
        {
            v = e[p].v;
            if(!visit[v] && e[p].c>0)
            {
                level[v] = level[u]+1;
				visit[v] = true;
                que[++tail] = v;
            }
			if(visit[t])  return  true;
            p = nxt[p];
        }
    }
	return  false;
}

int dinic_dfs(int delta, int u)
{
    int tmp, sum = 0, p, v;
    if(u == t)  return  delta;
    p = h[u];
    while(p != -1)
    {
		if(delta == 0)  break;
        v = e[p].v;
        if(h[u]+1==h[v] && e[p].c>0)
        {
            tmp = dinic_dfs(min(delta, e[p].c), v);
            sum += tmp;
            delta -= tmp;
            e[p].c -= tmp;
            e[p^1].c += tmp;
        }
        p = nxt[p];
    }
    return  sum;
}

void Max_flow(int s, int t)
{
    int ans = 0;
    while(bfs(s, t))
        ans += dinic_dfs(INF, s);
}

int main()
{
    int T, i, a, b, c;
	freopen("data.txt", "r", stdin);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        n++;
        s = 0;
        t = n;
        for(i = 0; i <= n; i++)
        {
            din[i] = dout[i] = 0;
            h[i] = -1;
        }
        tot = 0;
        for(i = 0; i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            din[b]++;
            dout[a]++;
            if(c == 1)  continue;
            else
            {
                add(a, b, 1);
                add(b, a, 0);
            }
        }
        for(i = 1; i < n; i++)
            if((din[i]-dout[i])%2 == 0)
            {
                if(din[i] > dout[i])
                {
                    add(i, t, (din[i]-dout[i])/2);
                    add(t, i, 0);
                }
                else if(din[i] < dout[i])
                {
                    add(s, i, (dout[i]-din[i])/2);
                    add(i, s, 0);
                }
            }
            else
            {
                break;
            }
        if(i < n)
        {
            printf("impossible\n");
            continue;
        }
        Max_flow(s, t);
        for(i = 0; i < tot; i++)
            if((e[i].u==s && e[i].c>0) || (e[i].v==t && e[i].c>0))
            {
                break;
            }
        if(i == tot)  printf("possible\n");
        else  printf("impossible\n");
    }
    return 0;
}

EK的AC代码：
#include <cstdio>
#include <cstring>

const int N = 210;
const int M = 1010;
const int INF = 0x7fffffff;

struct node
{
    int u, v, c;
}e[M*2];

int s, t, n, m, tot, din[N], dout[N], que[N], h[N], level[N], pre[N], nxt[M*2];
bool visit[N];

int min(int x, int y)
{
    return  x < y ? x : y;
}

void add(int u, int v, int c)
{
    e[tot].u = u;
    e[tot].v = v;
    e[tot].c = c;
    nxt[tot] = h[u];
    h[u] = tot++;
}

bool bfs(int s, int t)
{
    int u, v, head, tail, p;
	head = tail = 0;
	memset(visit, false, sizeof(visit));
	memset(pre, -1, sizeof(pre));
	que[0] = s;
	visit[s] = true;
	while(head <= tail)
	{
		u = que[head++];
		p = h[u];
		while(p != -1)
		{
			v = e[p].v;
			if(!visit[v] && e[p].c>0)
			{
				visit[v] = true;
				que[++tail] = v;
				pre[v] = p;
			}
			p = nxt[p];
			if(visit[t])  return  true;
		}
	}
	return  false;
}

void Max_flow(int s, int t)
{
    int ans = 0, v, tmp, delta;
    while(bfs(s, t))
	{
		v = t;
		delta = INF;
		tmp = pre[v];
		while(tmp != -1)
		{
			delta = min(e[tmp].c, delta);
			tmp = pre[e[tmp].u];
		}
		ans += delta;
		v = t;
		tmp = pre[v];
		while(tmp != -1)
		{
			e[tmp].c -= delta;
			e[tmp^1].c += delta;
			tmp = pre[e[tmp].u];
		}
	}
}

int main()
{
    int T, i, a, b, c;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        n++;
        s = 0;
        t = n;
        for(i = 0; i <= n; i++)
        {
            din[i] = dout[i] = 0;
            h[i] = -1;
        }
        tot = 0;
        for(i = 0; i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            din[b]++;
            dout[a]++;
            if(c == 1)  continue;
            else
            {
                add(a, b, 1);
                add(b, a, 0);
            }
        }
        for(i = 1; i < n; i++)
            if((din[i]-dout[i])%2 == 0)
            {
                if(din[i] > dout[i])
                {
                    add(i, t, (din[i]-dout[i])/2);
                    add(t, i, 0);
                }
                else if(din[i] < dout[i])
                {
                    add(s, i, (dout[i]-din[i])/2);
                    add(i, s, 0);
                }
            }
            else
            {
                break;
            }
        if(i < n)
        {
            printf("impossible\n");
            continue;
        }
        Max_flow(s, t);
        for(i = 0; i < tot; i++)
            if((e[i].u==s && e[i].c>0) || (e[i].v==t && e[i].c>0))
            {
                break;
            }
        if(i == tot)  printf("possible\n");
        else  printf("impossible\n");
    }
    return 0;
}

• Re:哪位大牛能解释下为什么我的EK16ms 但是dinic却TLE？？难道有针对dinic的数据？？ (47) Moon_1st 2011-04-01 21:55:14