题目
As you know, all the computers used for ACM contests must be identical, so the participants compete on equal terms. That is why all these computers are historically produced at the same factory.
Every ACM computer consists of P parts. When all these parts are present, the computer is ready and can be shipped to one of the numerous ACM contests.
Computer manufacturing is fully automated by using N various machines. Each machine removes some parts from a half-finished computer and adds some new parts (removing of parts is sometimes necessary as the parts cannot be added to a computer in arbitrary order). Each machine is described by its performance (measured in computers per hour), input and output specification.
Input specification describes which parts must be present in a half-finished computer for the machine to be able to operate on it. The specification is a set of P numbers 0, 1 or 2 (one number for each part), where 0 means that corresponding part must not be present, 1 — the part is required, 2 — presence of the part doesn't matter.
Output specification describes the result of the operation, and is a set of P numbers 0 or 1, where 0 means that the part is absent, 1 — the part is present.
The machines are connected by very fast production lines so that delivery time is negligibly small compared to production time.
After many years of operation the overall performance of the ACM Computer Factory became insufficient for satisfying the growing contest needs. That is why ACM directorate decided to upgrade the factory.
As different machines were installed in different time periods, they were often not optimally connected to the existing factory machines. It was noted that the easiest way to upgrade the factory is to rearrange production lines. ACM directorate decided to entrust you with solving this problem.
Input
Input file contains integers P N, then N descriptions of the machines. The description of ith machine is represented as by 2 P + 1 integers Qi Si,1 Si,2...Si,P Di,1 Di,2...Di,P, where Qi specifies performance, Si,j — input specification for part j, Di,k — output specification for part k.
Constraints
1 ≤ P ≤ 10, 1 ≤ N ≤ 50, 1 ≤ Qi ≤ 10000
思路
这个题目我傻了，看啊看不懂，累了。首先的话，很明显，我们肯定是从不需要零件的机器开始，自然而然它们和源点相连接，那么输出全都是0的机器需要和汇点相连，输入和输出想对应 的机器也需要相连接。最后跑最大流就好了。关于输出路径，看一下反向边的流量是否大于0就好了。直接输出。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
#include<stack>
#include<set>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<int,ll> PLL;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
} while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=1e3+10;
struct edge {
int v,flow,next;
}e[maxn];
int head[maxn],cnt=-1;
struct node {
int u,v,w;
}q[maxn*maxn];
inline void add (int u,int v,int flow) {
e[++cnt]=(edge) {v,flow,head[u]};
head[u]=cnt;
}
inline void add_edge (int u,int v,int flow) {
add (u,v,flow);
add (v,u,0);
}
int dis[maxn],cur[maxn];
int s,t,n,m,ans,x,y;
int bfs () {
MT (dis,0);
queue<int > q;
q.push (s);
dis[s]=1;
while (q.size ()) {
int x=q.front (); q.pop ();
for (int i=head[x];i!=-1;i=e[i].next) {
if (dis[e[i].v]==0&&e[i].flow) {
dis[e[i].v]=dis[x]+1;
q.push (e[i].v);
}
}
}
return dis[t];
}
int dfs (int now,int nowflow) {
if (now==t) return nowflow;
for (int &i=cur[now];~i;i=e[i].next) {
if (dis[e[i].v]==dis[now]+1&&e[i].flow) {
int canflow=dfs (e[i].v,min (nowflow,e[i].flow));
if (canflow>0) {
e[i].flow-=canflow;
e[i^1].flow+=canflow;
return canflow;
}
}
}
return 0;
}
void Dinic () {
while (bfs ()) {
for (int i=s;i<=t;i++) cur[i]=head[i];
while (int val=dfs(s,inf)) ans+=val;
}
}
int p,val[maxn];
int st[maxn][maxn];
int main () {
MT (head,-1);
scanf ("%d%d",&p,&n);
rep (i,1,n) {
scanf ("%d",&val[i]);
rep (j,1,2*p) scanf ("%d",&st[i][j]);
}
rep (i,1,n) {
add_edge (i,i+n,val[i]);
int flag1=1,flag2=1;
rep (j,1,p) {
if (st[i][j]==1) flag1=0;
if (st[i][j+p]!=1) flag2=0;
}
if (flag1) add_edge (0,i,inf);
if (flag2) add_edge (i+n,2*n+1,inf);
}
rep (i,1,n) {
rep (j,1,n) {
if (i==j) continue;
bool flag=true;
rep (k,p+1,2*p) {
int now=k-p;
if (st[j][now]==2) continue;
if (st[i][k]!=st[j][now]) flag=false;
}
if (flag) add_edge (i+n,j,inf);
}
}
s=0,t=2*n+1;
Dinic ();
printf ("%d ",ans);
ans=0;
rep (i,1+n,2*n) {
for (int j=head[i];~j;j=e[j].next) {
int v=e[j].v;
if (v!=2*n+1&&v!=0&&e[j^1].flow&&v!=i-n) {
q[++ans].u=i-n;
q[ans].v=v;
q[ans].w=e[j^1].flow;
}
}
}
printf ("%d
",ans);
rep (i,1,ans) printf ("%d %d %d
",q[i].u,q[i].v,q[i].w);
return 0;
}