这个SAP模板应该没有问题的，我AC了好多题目个说。
我听从了discuss里面的建议，按顺序输出每个点，并先输出-再输出+。结果还是WA
/*另注：我样例的结果是
5
3
1 +
3 -
3 +
我觉得也是正确的
但是跟AC的程序以及样例输出不一样。
*/
#include <cstdio>
#include <cstring>
#define oo 2147483647
#define min(a,b) ((a)>(b)?(b):(a))
#define maxn 211

using namespace std;

int n,m;

int totalv,source,sink;
int g[maxn + 1][maxn + 1],g_bak[maxn + 1][maxn + 1];

int height[maxn + 1];
int height_cnt[maxn + 1];

bool mark[maxn + 1];
bool mark1[maxn + 1];

int shortest_augmenting_path(int x,int flow)
{
    if (x==sink) return flow;
    int minh = totalv;
    for (int i=1;i<=totalv;i++){
        if (!g[x][i]) continue;
        if (height[i] + 1==height[x]){
            int k = shortest_augmenting_path(i,min(flow,g[x][i]));
            if (k){
                g[x][i] -= k;
                g[i][x] += k;
                return k;
            }
            if (height[source]>=totalv) return 0;
        }
        minh = min(minh,height[i]);
    }
    height_cnt[height[x]] --;
    if (!height_cnt[height[x]]) height[source] = totalv;
    height[x] = minh + 1;
    height_cnt[height[x]] ++;
    return 0;
}

int max_flow()
{
    int ans = 0;
    memset(height,0,sizeof(height));
    memset(height_cnt,0,sizeof(height_cnt));
    height_cnt[0] = totalv;
    while (height[source]<totalv)
        ans += shortest_augmenting_path(source,oo);
    return ans;
}

void dfs(int x)
{
    mark[x] = 1;
    for (int i=1;i<=totalv;i++){
        if (!g[x][i]) continue;
        if (mark[i]) continue;
        dfs(i);
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)==2){
        memset(g,0,sizeof(g));
        source = n*2 + 1;
        totalv = sink = source + 1;
        for (int i=1;i<=n;i++)
            scanf("%d",&g[source][i]);
        for (int i=1;i<=n;i++)
            scanf("%d",&g[i + n][sink]);
        for (int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            g[a][b + n] = oo;
        }

        int ans = max_flow();
        printf("%d\n",ans);
        int total_ans = 0;
        memset(mark,0,sizeof(mark));
        dfs(source);
        for (int i=1;i<=n;i++){
            if (!mark[i]) total_ans ++;
            if (mark[i + n]) total_ans ++;
        }
        printf("%d\n",total_ans);
        for (int i=1;i<=n;i++){
            if (mark[i + n]) printf("%d -\n",i);
            if (!mark[i]) printf("%d +\n",i);
        }
    }
    return 0;
}

• 对不起，我2B了，图建反了…… (35) fyq 2010-12-24 11:35:32