3996: [TJOI2015]线性代数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1054 Solved: 684[][][]Description
给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得
D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D
Input
第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.
接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。
Output
输出最大的D
Sample Input
3 1 2 1 3 1 0 1 2 3 2 3 7
Sample Output
2
HINT
1<=N<=500
Source
Solution
首先来化简一下题目中的式子：
设$E=A*B$，很显然E为一个1×N的矩阵，那么有$E_{1,j}=\sum_{i=1}^{N}A_{1,i}B_{i,j}$
那么$A*B-C$就可以化成$F_{1,j}=\sum_{i=1}^{N}A_{1,i}B_{i,j}-C_{1,j}$
那么进一步化简$D_{1,1}=\sum_{j=1}^{N}\left ( \left ( \sum_{i=1}^{N}A_{1,i}B_{i,j}-C_{1,j} \right )*A'_{j,1} \right )$
最后化成：$D=\sum_{i=1}^{N}\sum_{j=1}^{N}A_{i}A_{j}B_{i,j}-\sum_{i=1}^{N}A_{i}C_{i}$
那么从式子的角度去思考建图由于$A$是一个0/1矩阵，不妨把$A$看做“选”或“不选”，那么$B_{i,j}$看做同时选$i$和$j$两个物品的收益，$C_{i}$可以看做选第$i$个物品的代价。
也就是说选$B_{i,j}$必须选$C_{i},C_{j}$
最大权闭合子图.....
Code
#include#include #include #include using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') { if (ch=='-')f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}#define maxn 300010#define maxm 3000010int N,tot,ans;struct Edgenode{ int to,next,cap;}edge[maxm];int head[maxn],cnt=1;void add(int u,int v,int w){cnt++;edge[cnt].to=v;edge[cnt].cap=w;edge[cnt].next=head[u];head[u]=cnt;}void insert(int u,int v,int w){add(u,v,w);add(v,u,0);}//#define inf 0x7fffffffint dis[maxn],q[maxn<<1],cur[maxn],S,T;bool bfs(){ for (int i=S; i<=T; i++) dis[i]=-1; q[0]=S; int he=0,ta=1; while (he
正解被喝水路过的ShallWe直接秒....不然我还没往最小割模型上靠...
