题目链接
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5449
题意
给出一个n 然后有n行 每行给出两个数 这两个数之间可以用三种操作 分别是 + - *
如果这n对数通过操作后 得到的结果都是不同的，那么这个方案就是符合条件的 输出任意一种可行方案
如果存在相同结果，那么就是不可行的
思路 可以把N对数看成一个点，把一对数通过三种操作后得到的结果也看成一个点，将他们之间连一条边
然后二分匹配 如果最大匹配数 == n 那么就有可行解
输出就好了
linker[] 里存放的就是匹配的方案
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 7e3 + 5e2 + 10; const int MOD = 6; const int MAXN = 7510;//点数的最大值 const int MAXM = 50010;//边数的最大值 struct Edge { int to, next; }edge[MAXM]; int head[MAXN], tot; void init() { tot = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } int linker[MAXN]; bool used[MAXN]; int uN; bool dfs(int u) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!used[v]) { used[v] = true; if (linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false; } int hungary() { int res = 0; memset(linker, -1, sizeof(linker)); for (int u = 0; u < uN; u++)//点的编号0~uN-1 { memset(used, false, sizeof(used)); if (dfs(u))res++; } return res; } ll A[MAXN], B[MAXN], C[MAXN]; int main() { int n; while (scanf("%d", &n) != EOF) { init(); map <ll, int> mp; int pos = 0; for (int i = 0; i < n; i++) { scanf("%lld%lld", &A[i], &B[i]); ll num; num = A[i] + B[i]; if (mp[num] == 0) { C[pos] = num; mp[num] = ++pos; } addedge(mp[num] - 1, i); num = A[i] - B[i]; if (mp[num] == 0) { C[pos] = num; mp[num] = ++pos; } addedge(mp[num] - 1, i); num = A[i] * B[i]; if (mp[num] == 0) { C[pos] = num; mp[num] = ++pos; } addedge(mp[num] - 1, i); } uN = pos; if (hungary() < n) puts("impossible"); else { for (int i = 0; i < n; i++) { ll num = C[linker[i]]; char c; if (A[i] + B[i] == num) c = '+'; else if (A[i] - B[i] == num) c = '-'; else c = '*'; printf("%lld %c %lld = %lld\n", A[i], c, B[i], num); } } } }转载于:https://www.cnblogs.com/Dup4/p/9433080.html
相关资源：JAVA上百实例源码以及开源项目