题目链接:

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=312468

感谢@zhaoxinyi 提供解题思路

感谢@似水流年 提供翻译

题意:

给你n对数字,每一对你可以算出它们的和/差/积

但是你要保证n对的结果不同,求一种构造方案

这一题我立下flag:AC了再去吃饭

然后17:50给过了才去吃饭..饿死了..所以叫做flag网络流

这一题建个网络流即可,s-->每一个数字-->每个方案-->每对数字-->t,然后直接看流量出解

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf=99999999;
struct edge
{
    int y;
    int weight;
    edge * next;
    edge * anti;
};
edge * li[100005];
int top=0;
edge * new_edge()
{
    static edge a[500005];
    return &a[top++];
}
edge * inserts(int x,int y,int w)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=w;
    t->next=li[x];
    li[x]=t;
    return t;
}
void insert_edge(int x,int y,int w)
{
    edge * t1=inserts(x,y,w);
    edge * t2=inserts(y,x,0);
    t1->anti=t2;
    t2->anti=t1;
}
int dist[100005];
int bfs(int s,int t)
{
    static int que[100005];
    int front=0,rail=1;
    memset(dist,-1,sizeof(dist));
    dist[s]=0;
    que[0]=s;
    for (;front<rail;front++)
    {
        int now=que[front];
        edge * x;
        for (x=li[now];x!=0;x=x->next)
        {
            if ((dist[x->y]==-1)&&(x->weight>0))
            {
                dist[x->y]=dist[now]+1;
                if (x->y==t) return 1;
                que[rail++]=x->y;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t)
{
    int tot=0;
    int pre[100005];
    edge * cur[100005];
    edge * path[100005];
    for (;bfs(s,t);)
    {
        int now=s;
        memcpy(cur,li,sizeof(cur));
        for (;dist[s]!=-1;)
        {
            if (now==t)
            {
                int temp;
                temp=now;
                int mini=inf;
                for (;temp!=s;temp=pre[temp])
                {
                    mini=min(mini,path[temp]->weight);
                }
                tot+=mini;
                temp=now;
                for (;temp!=s;temp=pre[temp])
                {
                    path[temp]->weight-=mini;
                    path[temp]->anti->weight+=mini;
                }
                now=s;
            }
            edge * x;
            for (x=cur[now];x!=0;x=x->next)
            {
                if ((dist[x->y]==dist[now]+1)&&(x->weight>0))
                {
                    pre[x->y]=now;
                    path[x->y]=x;
                    cur[now]=x;
                    now=x->y;
                    break;
                }
            }
            if (x==0)
            {
                dist[now]=-1;
                now=pre[now];
            }
        }
    }
    return tot;
}
map<long long,int> ma;
int count_sum=0;
void get_try(long long x)
{
    if (ma.find(x)==ma.end())
    {
        ma[x]=count_sum++;
    }
}
int a[2505],b[2505];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        int n;
        count_sum=0;
        memset(li,0,sizeof(li));
        top=0;
        if (scanf("%d",&n)==-1) break;
        int i;
        ma.erase(ma.begin(),ma.end());
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            get_try((long long)a[i]+b[i]);
            get_try((long long)a[i]-b[i]);
            get_try((long long)a[i]*b[i]);
        }
        int s=count_sum+4*n;
        int t=s+1;
        for (i=0;i<count_sum;i++)
        {
            insert_edge(s,i,1);
        }
        for (i=0;i<n;i++)
        {
            insert_edge(ma[(long long)a[i]+b[i]],count_sum+i*3,1);
            insert_edge(ma[(long long)a[i]-b[i]],count_sum+i*3+1,1);
            insert_edge(ma[(long long)a[i]*b[i]],count_sum+i*3+2,1);
            insert_edge(count_sum+i*3,count_sum+n*3+i,1);
            insert_edge(count_sum+i*3+1,count_sum+n*3+i,1);
            insert_edge(count_sum+i*3+2,count_sum+n*3+i,1);
            insert_edge(count_sum+n*3+i,t,1);
        }
        if (max_flow(s,t)<n)
        {
            printf("impossible\n");
            continue;
        }
        for (i=0;i<n;i++)
        {
            edge * x;
            for (x=li[count_sum+n*3+i];x!=0;x=x->next)
            {
                int t=x->y-count_sum-i*3;
                if ((t>=0)&&(t<=2))
                {
                    if (x->weight!=0)
                    {
                        if (t==0)
                        {
                            printf("%d + %d = %d\n",a[i],b[i],a[i]+b[i]);
                        }
                        else if (t==1)
                        {
                            printf("%d - %d = %d\n",a[i],b[i],a[i]-b[i]);
                        }
                        else
                        {
                            printf("%d * %d = ",a[i],b[i]);
                            cout<<(long long)a[i]*b[i]<<'\n';
                        }
                    }
                }
            }
        }
    }
    return 0;
}