题意：

输入一个n，后面输入n行，每一行两个数a、b。你可以对a、b进行三种操作：+、-、*

你需要保证对每一行a、b选取一个操作得到一个结果

你要保证这n行每一个式子选取的操作之后得到的结果都不一样。如果找不到就输出impossible

Sample Input 1

1 4

1 5

3 3

4 5

-1 -6

Sample Output

1 + 5 = 6

3 * 3 = 9

4 - 5 = -1

-1 - -6 = 5
Sample Input 2

2 4

-4 2

-4 2

-4 2

-4 2

Sample Output

impossible

题解：

网络流跑一边最大流就可以了

首先建一个汇点st，然后让st点和n个式子相连，把这n个式子看成一个点，然后一个式子对应三个结果，我们分别对着三个结果看成一个点，然后连线。之后把所有的结果点连接到一个尾点en

然后就是路径输出就行了，如果一个路径有流量，那么这个路径的流量信息肯定有改变，就判断这一点就可以输出路径

建图其实很简单，这里主要说一下不同网络流的复杂度

简单总结

FF算法： 利用dfs实现，时间复杂度O（V*E^2）

EK算法：利用bfs实现，时间复杂度O（V*E^2）

Dinic算法：递归实现，时间复杂度O（V^2*E）

SAP算法：时间复杂度O（V^2*E）但是加上弧优化和间隙优化之后时间复杂度非常可观

我以前认为点的数量肯定比边的数量小，所以dinic算法复杂度最小，所以就只记住了一个dinic算法

但是这一道题使用dinic算法就TLE了

1 #include
2 #include
3 #include
4 #include
5 #include

AC代码：

#include
#include
#include
#include
#include

inline void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,nxt[cnt]=head[a],head[a]=cnt++;
to[cnt]=a,val[cnt]=0,nxt[cnt]=head[b],head[b]=cnt++;
}
int dfs(int x,int mf)
{
if(x==en) return mf;
int i,k,temp=mf;
for(i=head[x]; i!=-1; i=nxt[i])
if(dis[to[i]]==dis[x]+1&&val[i])
{
k=dfs(to[i],min(temp,val[i]));
if(!k) dis[to[i]]=0;
temp-=k,val[i]-=k,val[i^1]+=k;
if(!temp) break;
}
return mf-temp;
}
int bfs()
{
while(!q.empty()) q.pop();
memset(dis,0,sizeof(dis));
q.push(st),dis[st]=1;
int i,u;
while(!q.empty())
{
u=q.front(),q.pop();
for(i=head[u]; i!=-1; i=nxt[i]) if(!dis[to[i]]&&val[i])
{
dis[to[i]]=dis[u]+1;
if(to[i]==en) return 1;
q.push(to[i]);
}
}
return 0;
}
inline int rd()
{
int ret=0,f=1;
char gc=getchar();
while(gc<'0'||gc>'9')
{
if(gc=='-') f=-f;
gc=getchar();
}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=m=rd(),st=0;
int i,j;
memset(head,-1,sizeof(head));
for(i=1; i<=n; i++)
{
ra[i]=rd(),rb[i]=rd();
if(!r[ra[i]+rb[i]])
r[ra[i]+rb[i]]=++m,ref[m]=ra[i]+rb[i];
if(!r[ra[i]-rb[i]])
r[ra[i]-rb[i]]=++m,ref[m]=ra[i]-rb[i];
if(!r[ra[i]*rb[i]])
r[ra[i]*rb[i]]=++m,ref[m]=ra[i]*rb[i];
add(i,r[ra[i]+rb[i]],1);
add(i,r[ra[i]-rb[i]],1);
add(i,r[ra[i]*rb[i]],1);
add(st,i,1);
}
en=m+1;
for(i=n+1; i<=m; i++) add(i,en,1);
while(bfs())
ans+=dfs(st,1<<30);
if(ans!=n)
{
printf("impossible");
return 0;
}
for(i=1; i<=n; i++)
{
for(j=head[i]; j!=-1; j=nxt[j])
{
if(!val[j])
{
if(ref[to[j]]==ra[i]+rb[i])
printf("%lld + %lld = %lld\n",ra[i],rb[i],ra[i]+rb[i]);
else if(ref[to[j]]==ra[i]-rb[i])
printf("%lld - %lld = %lld\n",ra[i],rb[i],ra[i]-rb[i]);
else if(ref[to[j]]==ra[i]*rb[i])
printf("%lld * %lld = %lld\n",ra[i],rb[i],ra[i]*rb[i]);
}
}
}
return 0;
}

二分图题解：

就是把n个式子看成n个点，把n个式子对应的三个结果看成3*n个点

二分图匹配就行

代码：

#include
#include
#include
#include
#include

/*
4
1 5
3 3
4 5
-1 -6

*/